Recursion

From CS 61A Wiki
(Redirected from Tree recursion)
Jump to: navigation, search

Recursion is a technique for solving a large computational problem by repeatedly applying the same procedure(s) to reduce it to successively smaller problems. 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.

Infinite recursion occurs if there is no base case or the recursive step does not make progress towards its base case(s).

Example for how a recursive function looks:

def fn(input):
    if <base case>:
        return ...
    else:
        return <combine input and fn(input_reduced)>


Simple recursion

In simple recursion — the most straightforward and common form of recursion — there is usually only one base case, and in the recursive step, the recursive procedure calls itself only once.

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.

Examples

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. Tree recursive functions generally have more base cases than simply recursive functions as well, though this is not a necessary condition. If a tree recursive function makes repeated computations, it is more optimal to store previous return values rather than perform expensive recomputations. This technique can be implemented through memoization.

Analogy

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, in order to compute your dad's call, we must make a call to each of your paternal grandparents.

Until num_gen is equal to 0, each function call to a person produces two additional calls to the num_ancestors function. In general, tree recursive functions are distinguished from simply recursive functions by generating more than one call to the same function in the recursive step. If we draw a line from each frame to the frames it directly generates, the pattern of calls looks like a tree called the call tree, with each "root" having two "branches." Here, the call tree mirrors the family tree.

Examples

Fibonacci numbers

Consider this Python code for generating the nth Fibonacci number:

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

The call tree for the fib function looks similar to the call tree for the num_ancestors function, with each function call that was not a base case generating two more calls to fib.

Call tree for fib

Towers of Hanoi

Main article: Towers of Hanoi

Power set

Main article: Power set

Mutual recursion

A pair of functions are mutually recursive if they each make recursive calls to each other and are thus defined in terms of one another.

The following example of two mutually recursive functions is taken from "Abstraction: Trees: Mutual Recursion" by Harvey and Wright (1999):


(define (count-leaves tree)

 (if (leaf? tree)
     1
     (count-leaves-in-forest (children tree))))

(define (count-leaves-in-forest forest)

 (if (null? forest)
     0
     (+ (count-leaves (car forest))
        (count-leaves-in-forest (cdr forest)))))

Tail recursion

A function is tail recursive if the result of any recursive calls made in a function is immediately returned. Tail recursive functions do not make further calculations after a recursive call.

In Scheme, tail recursion is considered iteration. Scheme also supports tail call optimization, which will get rid of the frames that are no longer necessary, making the procedure more space efficient.

Example

The following factorial function is not tail recursive because the result from the recursive call still needs to be multiplied by n:

(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))

(fact 2) would execute as follows:

(fact 2)
(* 2 (fact 1))
(* 2 (* 1 (fact 0)))
(* 2 (* 1 1))
(* 2 1)
2

To make fact tail recursive, we use a helper function that has an extra parameter that keeps track of the running product:

(define (fact n)
    (define (fact-tail n curr-product)
        (if (= n 0)
            curr-product
            (fact-tail (- n 1) (* curr-product n))))
    (fact-tail n 1))

(fact 2) would execute as follows:

(fact 2)
(fact-tail 2 1)
(fact-tail 1 2)
(fact-tail 0 2)
2

See also