1.5 Recursion

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.

If you know the base case(s) and the recursive case(s) for this recursion problem, you can easily write the code for this recursion problem. Here is the code from the example we just talked about:


# Code to figure out how many of a factor a number has


def number_factor(number, factor, factor_counter = 0):
    """
    Parameters:
    1) number is the number in which we are finding the number of
    factors of. EX: 24
    2) factor is the factor in which we are finding the number of
    in the parameter number. EX: 2
    Output: The number of times the parameter number can be divisible
    by the parameter factor. This number is also the parameter
    factor_counter right before it is returned. EX: 3
    """

    if number % factor != 0:  # Base Case
        return factor_counter
    else:  # Recursive Case
        return number_factor(number / factor, factor, factor_counter + 1)


print(number_factor(24, 2))

Here is another example of a function that takes a number n and prints an array with the values n and every integer less than it until 0.


def countdown(n, arr=[]):
    if n < 0:  # base case 1
        return "out of bounds"
    if n == 0:  # base case 2
        return arr
    # recursive case
    arr.append(n)
    return countdown(n - 1, arr)

print(countdown(5))

View code on GitHub.

Practice

Factorial

Create a recursive method that mirrors how a factorial would work in math.

💻 Template code

✅ Solution code

List Sum

Create a recursive sequence that finds the sum of a list that may contain another list within it. Ex: [3, 5, [2, 6], 9, [9, 3, [2], 0], 12] should return 3 + 5 + 2 + 6 + 9 + … + 12

💻 Template code

✅ Solution code

Previous Section

4️⃣

1.4 Time Complexity

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.