From CS 61A Wiki
Revision as of 20:12, 2 June 2014 by Acotra (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to: navigation, search

Recursion is a technique for solving large computational problems by reducing them to successively smaller problems by repeatedly applying the same procedure(s). A recursive procedure has two parts, one or more base cases and a recursive step. Base cases are pre-determined solutions for the simplest possible 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.


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
        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
        return n*factorial(n - 1)

Notice that the factorial procedure is only called 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:

<syntaxthighlight lang="python"> def pow(b, p):

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


Here, the recursive call to pow appears twice - once in each 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

Mutual Recursion

Tail Recursion