Recursion

Nov. 13, 2020

Vuong Huynh

The idea of Recursion is to create a function and call itself.

Below is the basic example in pseudocode:

function recursive(input):
    if input <= 0
        return input
    else
        output = recursive(input - 1)
        return output

First, the recursive function called itself:

output = recursive(input - 1)

Second, the recursive function needs a base case:

if input <= 0

return input

Recursive functions can be thought of as a while loop. In a while loop, we will loop again and again until the condition is met. The condition in the while loop is about the same as the base case in recursive functions. If we don't have the base case, we will be stuck in infinite recursion.

Third, the input in the recursive function needs to be altered which is the same as the "counter" in the while loop to avoid infinite recursion.

Practice:

We're going to take a look at recursion with a famous example—the Fibonacci Sequence.
The Fibonacci Sequence follows one rule: get the next number in the sequence by adding the two previous numbers. Here is an example of the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Step through each value. We start with 0 and 1. 0 + 1 = 1, so we add 1 to the sequence. 1 + 1 = 2, so 2 is added. 1 + 2 = 3, so 3. 2 + 3 = 5, et cetera.
We could represent these numbers as a Python list, and it would look something like this:fib_seq = [] fib_seq[0] = 0 fib_seq[1] = 1 fib_seq[2] = 1 fib_seq[3] = 2 fib_seq[4] = 3 fib_seq[5] = 5 fib_seq[6] = 8 fib_seq[7] = 13 fib_seq[8] = 21 fib_seq[9] = 34

We can generate this sequence using an iterative method (with loops - not recursive way):

def get_fib_loop(position):
    if position == 0: return 0
    if position == 1: return 1

    first = 0
    second = 1
    next = first + second
  
    for i in range(2, position):
        first = second
        second = next
        next = first + second   
    return next

print(get_fib_loop(7))

In the practice, we'll be implementing get_fib() in several recursive ways.

Applying the pseudocode of the recursive function above, we can easily build the Fibonacci Sequence:

def get_fib_recursive(input):
    if input <= 1:
        return input
    else:
        output = get_fib_recursive(input - 1) + get_fib_recursive(input - 2)
        return output
    
print(get_fib_recursive(7))

We can use a more elegant solution provided from Udacity:

def get_fib_recursion(position):
    if position == 0 or position == 1:
        return position
    return get_fib_recursion(position - 1) + get_fib_recursion(position - 2)

Another good example of using Recursion is calculating Factorial n! Remember 0! = 1 and 1! = 1

n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1

n! = n x (n−1)! n! = n x (n−1) x (n−2)! n! = n x (n−1) x (n−2) x (n−3)! ⋅ ⋅ n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3! n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2! n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

We can use a for loop to solve this problem:

def factorial_loop(n):
    output = 1
    if n == 0:
        return 1
    else:
        for i in range(1, n + 1):
            output = output * i
        return output

print(factorial_loop(7))          # 5040

Or solve the Factorial in recursive way:

def factorial_recursive(n):
    if n == 1:
        return 1
    else:
        return n * factorial_recursive(n-1)

print(factorial_recursive(7))       # 5040

A very interesting thread in Stack Overflow about Efficiency of Recursion
Some good notes found from utexas.edu:

A recursive method is a method that calls itself. An iterative method is a method that uses a loop to repeat an action. Anything that can be done iteratively can be done recursively, and vice versa. Iterative algorithms and methods are generally more efficient than recursive algorithms.

Recursion is based on two key problem solving concepts: divide and conquer and self-similarity. A recursive solution solves a problem by solving a smaller instance of the same problem. It solves this new problem by solving an even smaller instance of the same problem. Eventually, the new problem will be so small that its solution will either be obvious or known. This solution will lead to the solution of the original problem.

A recursive definition consists of two parts: a recursive part in which the nth value is defined in terms of the (n-1)th value, and a non recursive boundary case or base case which defines a limiting condition. An infinite repetition will result if a recursive definition is not properly bounded. In a recursive algorithm, each recursive call must make progress toward the bound, or base case. A recursion parameter is a parameter whose value is used to control the progress of the recursion towards its bound.

Function call and return in Python uses a last-in-first-out protocol. As each method call is made, a representation of the method call is place on the method call stack. When a method returns, its block is removed from the top of the stack.

Use an iterative algorithm instead of a recursive algorithm whenever efficiency and memory usage are important design factors. When all other factors are equal, choose the algorithm (recursive or iterative) that is easiest to understand, develop, and maintain.