RECURSION

WHAT IS RECURSION?

Where a method calls itself to split a huge problem into smaller sub-problems until it reaches a base case. These smaller problems build toward the main logic of the full problem. This is a more efficient way than creating crazy or convoluted loops. It is essentially a cleaner way to execute long functions.

THE TWO PARTS OF RECURSION

THE BASE CASE

The exit condition for the program. Recursion is boiled down to the structural action of the method calling itself. A base case is designed to be the threshold or the limit at which that action shall stop. For example, if you are looking through multiple files for ONE specific file, the base case is finding that one file. Whatever recursive method it uses, its search will continue until it finds that file.

RECURSIVE CALL

The partner to a base case, yet equally as important. It is the driving factor of the entire recursion process. This is where a method invokes itself to move it closer to the base case. Every time a recursive call happens, the method it's currently doing (or its current recursive call) stops. It then waits until the next recursive call has reached the base case, and if not, the process repeats again. But if it does, it will then re-continue the method for each one it's stopped and create a unified return of all the results.

For example, you are in a long movie line, but you don't know what number you are in the line. The only person who for sure knows what number they are in the line is the first person in the line. So the recursive call is to ask the person in front of you, "What number are they?" If they aren't the first person in the line, they won't know, so they will then ask the person in front of them iof they know. Once the base case of the first person is found, they will all now turn back and count their places until they get back to you.

BEST EXAMPLES

FACTORIALS

A factorial is the product/result of all the numbers from n to zero. For example a factorial of 4! is 4 × 3 × 2 × 1. Additionally, it is also possible to split the answer and do 4 x 3!, which comes out to the same answer. Recursively, we can achieve this in code using only a few lines. Here the base case is 1, and the recursive call is until n reaches one; it will find the factorial of n and multiply it together.

For example, let's put in the number 3.

Checks if n=3 is 1; it is not, so it returns 3 times the recursive call factorial(2) (stores 3)

EXECUTE FACTORIAL (2): Checks if n=2 is 1; it is not, so it returns 2 times the recursive call factorial(1) (stores 2)

EXECUTE FACTORIAL (1): Checks if n=1 is 1; it is, so it returns 1 (stores 1)

After it returns 1, it tracks back to find the other answers, it grabs the 2 then grabs the 3 to create a final equation of 3X2X1 which equals 6.

COUNTING EARS AND FINDING TOTAL

Here is a classic problem of finding the total sum of something via recursion.

A bunny has 2 ears each, and we wanna calculate the sum of how many ears there would be with ANY number of bunnies (will will use n in this case). Here, the base case is when we run out of bunnies to count, aka when n is 0. The recursive call is storing a 2, then recalling the method for the next bunny.

For example, let's put in the number 3.

Checks if n=3 is 0; it is not, so it returns 2 plus the recursive call bunnyEars(2) (stores 2)

EXECUTE bunnyEars(2): Checks if n=2 is 0; it is not, so it returns 2 plus the recursive call bunnyEars(1) (stores 2)

EXECUTE bunnyEars(1): Checks if n=1 is 0; it is not, so it returns 2plus the recursive call bunnyEars(0) (stores 2)

EXECUTE bunnyEars (0): Checks if n=0 is 0; it is, so it returns 0 (+ stores 0)

After it returns 0, it tracks back to count all the bunny ears. For each recursive call we made we stored a 2, so let's add the amount of 2's we stored which is three. 2+2+2 is 6 so we have 6 bunny ears.

FINDING POWERS

For me, this is one of the harder problems, as it is really hard to grasp at first, but is quite simple with some practice. This is an excellent use of the base case. Here we are given two variables: the base and the power. Here we have to calculate base ^ power ONLY by recursion. Here, our base case is when it reaches zero; it should return 1, and our recursive call is that it repeatedly stores the base until the base is reached.

*n is power, For example, let's use 3 as our base, and 2 as our power/n.

Checks if n=2 is 0; it is not, so it returns the base times the recursive call powerN(1) (+ stores base (3))

EXECUTE powerN (1): Checks if n=1 is 0; it is not, so it returns the base times the recursive call powerN((1) (+ stores base(3))

EXECUTE powerN(0): Checks if n=0 is 0; it is, so it returns 1 (+ stores 1)

After it returns 0, it tracks back to count all bases we stored. In this case, we stored the base 2 times, meaning we do 3 times 3 which equals 9 (which IS 3^2).

Page updated

Google Sites

Report abuse