Recursion

Recursion in programming means a function that call itself inside of it. Recursion pops up in lots of places in both math and computer science. Sometimes some problems are not able or not easily to solve in a loop way, but can be able to solve in recursive way in least steps. The recursion is an idea of “divide and conquer”. The problems that are solved by recursion can be divided in to two part: “base case”, and “recursive steps”. Normally the “base case” is the condition that helps the function “escape” from the recursion, otherwise, it will cause infinity loop (stack overflow). And the “recursive steps” are the deductive steps of the problems.

Here we introduce an example of the Fibonacci sequence:
F_0 = 1, F_1 = 1, F_n = F_n-1 + F_n-2

the sequence looks like:
1, 1, 2, 3, 5, 8, 13, 21, 33, ...

Suppose we would like to get the nth Fibonacci number, it may not be easily solve by a for loop or while loop. As the principal of recursion, we can divide this problem into two parts:

1. base case: when n = 0 or n = 1, we can get the Fibonacci number immediately, F_0 = 0, F_1 = 1
2. recursive step: when n > 1, the nth Fibonacci number is defined by F_n = F_n-1 + F_n-2

Based on the information above, we can define our function as below:

def Fib(n):
    # base case:
    if n == 0 or n == 1:
        return 1
    # recursive step:
    return Fib(n - 1) + Fib(n - 2)

Another example of recursion is factorial of an integer n. Although it can be solved in loop way, recursion can make our codes more concise.

def fac(n):
    # base case:
    if n == 0 or n == 1:
        return 1
    # recursive step:
    return n * fac(n - 1)

Small note:

There is a limit to how many recursive function calls Python will allow. Namely, we can have a recursion depth of AT MOST 998 function calls and any more recursive function calls will cause a RecursionError to be thrown. You are not allowed to do infinite loops with recursion in python.

Sometimes recursion can be slow. As in our Fib() function, when the n value is getting larger and larger, the runtime will get longer and longer. To solve the fact that recursion could be slow, “tail recursion” and “memorization” are introduced. As in our Fib() function, if we would like to get the 4th Fibonacci number, we need to get the 3rd Fibonacci number and the 2nd Fibonacci number. In order to get the 3rd Fibonacci number, we need to get the 2nd Fibonacci number and the 1st Fibonacci number. Notice that the 2nd Fibonacci number is being recalculated. As the number getting larger and larger, more and more number are being recalculated. Therefore, “tail recursion” and “memorization” basically follow the same idea: storing the number in some ways so that they are only calculated once. Just for simplifying, “tail recursion” stores the values in arguments, and “memorization” stores the values in a dictionary.

# tail recursion for Fibonacci sequence
def Fib_tail(n, f0=1, f1=1):
    # base case:
    if n == 0:
        return f0
    if n == 1:
        return f1
    # recursive step:
    return Fib_tail(n-1, f1, f0+f1)

# memorization for Fibonacci sequence
def Fib_memo(n, D={}):
    # base case:
    if n in D:
        return D[n]
    # recursive step:
    elif n == 0 or n == 1:
        result = 1
    else:
        result = Fib_memo(n - 1) + Fib_memo(n - 2)
    D[n] = result
    return D[n]

Recursion is also used for searching through a filesystem. Imagine a file was buried down in multiple folders. It cannot be found through some nested loops, because we don’t know exactly how many folds there are. This is similar to searching for a specific number inside arbitrarily nested lists. For instance, suppose we wanted to find the number 27 inside of the nested lists: L = [2, 4, [83, 27, [19, 9], [35]], [3, [32, 0], 28], 19].

def search_27(L):
    for i in L:
        # base case:
        if i == 27:
            print("found it!")
            return
        # recursive steps:
        if type(i) is list:
            search_27(i)