Recursion

Recursion: 

Overview:
Recursion is a problem solving method which involves breaking down a problem into sub-problems. These sub-problems should be able to be solved in the same way as the larger problem. Usually it is a process where a function calls itself while inside the function, sort of like that movie Inception.

Credit: http://icannotdraw.thecomicseries.com/comics/25/

Why would we ever want to call a function inside of itself?
Here is a simple example:
A factorial is the product resulting from repeated multiplications. Specifically, if n >= 0, then
n! = n * (n-1) * (n-2) * ............. * 3 * 2 * 1.
We can break this problem down into sub-problems. Note that n! = n * (n-1)!
But then, (n-1)! = (n-1) * (n-2)!, and so on. Eventually as n decreases, we will reach 1, where we have to stop. (the base case)
Basically, in order to obtain n!, simply multiply n by (n-1)! By the definition of factorial will then compute (n-1)! by computing (n-1) * (n-2)! factorial, and so on.

Here is the code:

def factorial(n):
     '''Precondition: n >= 0, and 0! is defined as 1.'''
     if n <= 1:
          return 1
     else:
          return n * factorial(n - 1)


Here is another example:
The fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ....
is where each number in the sequence is the sum of the 2 numbers before it.

Let's say we wanted the 5th term of this sequence. The 5th term is the sum of the 4th and 3rd terms. Assume we did not know the 4nd and 3rd terms. We can still get their values by using the same algorithm: For the 4th term, this is the sum of the 2nd and 3rd terms. For the 3rd term, this is the sum of the 1st and 2nd terms. Once we run into the 2nd term, we can't say that this is equal to the 1st and 0th term, since this does not make sense. So, we define the base case as: if the term, n, is less than or equal to 2, simply return n-1.

Here is the code:
def fib(n: int):
     if n <= 2:
          return n - 1
     else:
          return fib(n - 2) + fib(n - 1)

Visually:

Advantages/Disadvantages of Recursion:
The factorial program can be written using an iterative process, with loops.

def factorial(n):
    if n == 0:
        return 1

    acc = 1
    for i in range(1, n + 1):
        acc = acc * i
    return acc

However, there exist problems that cannot easily be solved using simple for/while loops. For example, I am not aware of a simpler algorithm that computes fibonacci numbers. Problems like Towers of Hanoi are made much easier using recursion. In Computer Science, trees and linked lists are useful for storing and manipulating data. In order to access the data in trees and linked lists, it is easier to use recursion because trees consist of subtrees, and linked lists refer to other linked list objects making them recursive in structure.
For example in lecture, binary trees were able to be 'traversed' easily using techniques like inorder, preorder, and postorder traversal. These traversals are much easier to implement (1 to 2 lines of code) than any other non-recursive solution you can think of.

Some drawbacks of recursion:
Recursive algorithms can be slow. For example, when I try to move 30 cheeses using 4 stools (from Assignment 1), python took several minutes to compute the solution. Another problem is the usage of memory. If I want to compute factorial(2000), I get a 'maximum recursion depth exceeded' error.

Also, recursive functions can be difficult to write :(

Thinking about Recursion:
How do you know if a recursive algorithm works? Well, you have to have faith! (Sort of)
If I know a recursive algorithm works for the simplest case, I can assume that the algorithm will always work
on any instance of the simplest case.
For example, if I want to calculate the sum of [1, 2, [3, 4], 5], and I know that my summation algorithm works on flat lists (a list with no nested lists), then I can assume my algorithm work on any number of nested lists.

Personally, I relate recursion to mathematical induction. If I know that P(1) is true and I know that P(n) implies P(n + 1), then I can conclude than P(n) is true for all n > 0.

Similarly, if I know that an algorithm works on the simplest case (base case), and I know that the algorithm will work for some higher level cases, then I can reasonably conclude it will work for all cases.


Closing Remarks:
Before this course, I was uncomfortable with recursion. Although I was able to trace code and follow the lectures, I struggled to write recursive functions. Over the past few weeks I feel more confident in my abilities due to hefty amount of time I spent practicing recursion. One of the main problems I had was over-thinking the problem. Sometimes I would trace code too deep, or I would write a function in 5+ lines which actually could have been completed in 1 line using techniques like list comprehensions and ternary if.