Recursion

From CS 61A Wiki
Revision as of 15:23, 4 June 2014 by Acotra (Talk | contribs)


Jump to: navigation, search

Recursion is a technique for solving large computational problems by reducing them to successively smaller problems and repeatedly applying the same procedure(s). A recursive procedure has two parts, one or more base cases and a recursive step. Base cases are predetermined solutions for the simplest versions of the problem — if the given problem is a base case, no further computation is necessary to get the result. The recursive step is a set of rules that eventually reduces all versions of the problem to one of the base cases when applied repeatedly.

Analogy

Consider this procedure for learning the definition of recursion: "If you are Andrew Huang, you already know the definition. If not, find someone who is standing closer to Andrew Huang than you are and ask them what the definition of recursion is." Here, the base case is being Andrew Huang - once you reach this situation, no further work is necessary to get the definition of recursion. If you are not yet at a base case, the recursive step is to ask someone who is closer to Andrew, reducing the problem closer to the base case.

Let's call the procedure def_recursion. We can think about it in terms of the stack from environment diagrams. Suppose Matthew, Rohin, and Andrew are standing in a line. Matthew wants to know the definition of recursion, so his call to def_recursion is pushed onto the stack. He isn't Andrew, so must find someone standing closer to Andrew than he is and ask them for the definition. So Matthew asks Rohin for the definition of recursion. Rohin's call to the same def_recursion function is pushed on top of Matthew's call. Rohin is also not Andrew, so he must ask someone standing closer to Andrew than he is — in this case, it's Andrew himself. Now Andrew's call to def_recursion is pushed on top of Rohin's call.

Andrew is a base case, so he already knows the definition and immediately returns it to Rohin, and Andrew's frame pops off the stack. Now Rohin has the definition of recursion, which he can return to Matthew. Once he returns, Rohin's frame pops off the stack. Now Matthew's frame is the only one on the stack, and he has the definition of recursion. This was the initial goal, so Matthew's frame can return and pop off, leaving the stack empty.

In pseudocode, def_recursion, which takes in the person who wants to know the definition of recursion as a parameter, can be written like this:

def def_recursion(you):
    if you == AndrewHuang:
        return knowledge
    else:
        return def_recursion(someone closer to AndrewHuang)

Notice that in the recursive step, the same procedure is called again, but on a simpler version of the problem every time. If there were no base case (no one knew what recursion was), or the recursive step didn't make the problem smaller (everyone asked people further from Andrew what the answer was), then the recursion can malfunction and go into an infinite loop.

Simple recursion

Simple recursion is a procedure much like the example given in the analogy — there is usually only one base case, and the recursive procedure calls itself only once in every function call. An example of simple recursion is the factorial function:

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

Notice that the factorial procedure is called only once in the body of the recursive procedure. However, it is possible for a call to the function to appear in multiple places in the function body — if only one of those calls is ever executed in each frame, the function still exhibits simple recursion. For example, consider the function that raises a base b to a power p through a recursive procedure called repeated squaring:

def pow(b, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(b, p // 2)
        return x * x
    else:
        x = pow(b, p // 2)
        return b * x * x

Here, the recursive call to pow appears twice — once in the elif clause, once in the else clause. However, the whole procedure is still simply recursive, because only one of those else clauses is ever triggered in each recursive call, meaning the procedure can only ever call itself once per frame.

Tree recursion

A function is tree recursive if the recursive step contains more than one call to the same function. For example, consider the function for generating Fibonacci numbers:

def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    return fib(n - 2) + fib(n - 1)

Let's consider how this algorithm would compute the 4th Fibonacci number. In order to compute fib(4), we need to compute fib(2) and fib(3). In order to compute fib(2), we need to compute fib(0) and fib(1). In order to compute fib(3). we need to compute fib(1) and fib(2). In order to compute fib(2) again, we need to compute fib(0) and fib(1) again. Each frame creates two more until the base cases are reached, creating a call structure that looks like a tree, with every "root" having two "branches".

A tree recursive procedure can naturally be used to answer the question "How many ancestors do I have, up to a certain number of generations?" One natural way to answer this question is to say "I have a mother and a father, making two ancestors. Additionally, my mother's ancestors are my ancestors, and my father's ancestors are my ancestors." Consider the following pseudocode:

def num_ancestors(you, num_gen):
    if num_gen == 0:
        return 0
    else:
        return 2 + num_ancestors(mom, num_gen - 1) + num_ancestors(dad, num_gen - 1)

The base case occurs when we only care about ancestors 0 generations up - that is, when we only care about you. Since you have no ancestors who are 0 generations older than you, we return 0. The recursive call then adds up your parents' ancestors, and adds 2 for your parents themselves.

If we wanted to count up all your ancestors two generations up, we would start with a call to num_ancestors(you, 2). In order to compute that, we need to computer num_ancestors(your_mom, 1) and num_ancestors(your_dad, 1). In order to compute num_ancestors(your_mom, 1), we must compute num_ancestors(your_maternal_grandma, 0) and num_ancestors(your_maternal_grandpa, 0) (similarly for your paternal grandparents). This is a tree recursive procedure whose call tree mirrors the family tree.

Mutual recursion

Tail recursion