Introduction to Recursion

Have you ever wondered what would happen if a function called itself inside of its body? This concept is called recursion. Recursion is solving a problem by having a function call itself over and over again. Each time the function is called, the problem is reduced. When the problem is reduced to a certain size, also known as its base case, we just solve it.

You often use and see recursion going on in real life without even realizing it. Here is an example of figuring out how many of a factor a number has.

• Example: Let’s say the number is 24 and we want to figure out how many 2’s it has. One way is to use recursion. Starting with 24, we keep dividing it by 2 and keeping track of how many 2’s divided so far until we get a number not divisible by 2:

START→24 and zero 2’s divided so far→  12 and one 2’s divided so far→ 6 and two 2’s divided so far→ 3 and three 2’s divided so far→STOP

• See that we had to divide by three 2’s to get from 24 to a number that is not divisible by 2. So the answer is 3.

Recursion has Advantages and Disadvantages

Advantages:

• A complex function can be split into sub-problems utilizing recursion.
• Recursion makes sequence creation simpler
• Recursion makes code simple and effective

Disadvantages:

• A lot of memory is used during recursion.
• A lot of time is spent running repeated processes.
• Hard to debug and understand

Base Case and Recursive Case

The base case(s) is the condition that causes the function to stop calling itself.

The recursive case(s) is the condition that allows the function to call itself.

Let’s go back to the example from the previous section which was figuring out how many of a factor a number has. Let’s use 24 as our number again and 2 as the factor again. The base case in this example is if the current number is no longer divisible by 2. If the function is at the base case, the number of 2’s that are divided to get the current number is returned. The recursive case in this example is if the current number is still divisible by 2. If the function is in the recursive case, the current number is divided by 2 and the number of 2’s divided so far is incremented by one. These parameters will be used to call itself (the function) again.

Remember, the recursive case will repeat itself until the base case is reached.