# Difference between revisions of "Recursion"

[checked revision] | [checked revision] |

m ({{C-class}}) |
(→Tree recursion: I would really appreciate if someone could add a nice picture of the recursion tree! Thanks :)) |
||

Line 49: | Line 49: | ||

==Tree recursion== | ==Tree recursion== | ||

+ | |||

+ | A [[Function | 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: | ||

+ | |||

+ | <syntaxhighlight lang="python"> | ||

+ | def fib(n): | ||

+ | if n == 0: | ||

+ | return 1 | ||

+ | if n == 1: | ||

+ | return 1 | ||

+ | return fib(n - 2) + fib(n - 1) | ||

+ | </syntaxhighlight> | ||

+ | |||

+ | Let's consider how this algorithm would compute the 4th Fibonacci number. In order to compute <code>fib(4)</code>, we need to compute <code>fib(2)</code> and <code>fib(3)</code>. In order to compute <code>fib(2)</code>, we need to compute <code>fib(0)</code> and <code>fib(1)</code>. In order to compute <code>fib(3)</code>. we need to compute <code>fib(1)</code> and <code>fib(2)</code>. In order to compute <code>fib(2)</code> ''again'', we need to compute <code>fib(0)</code> and <code>fib(1)</code> 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: | ||

+ | |||

+ | <syntaxhighlight lang="python"> | ||

+ | 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) | ||

+ | </syntaxhighlight> | ||

+ | |||

+ | The base case occurs when we only care about ancestors 0 generations up - that is, when we only care about <code>you</code>. 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 <code>num_ancestors(you, 2)</code>. In order to compute that, we need to computer <code>num_ancestors(your_mom, 1)</code> and <code>num_ancestors(your_dad, 1)</code>. In order to compute <code>num_ancestors(your_mom, 1)</code>, we must compute <code>num_ancestors(your_maternal_grandma, 0)</code> and <code>num_ancestors(your_maternal_grandpa, 0)</code> (similarly for your paternal grandparents). This is a tree recursive procedure whose call tree mirrors the family tree. | ||

==Mutual recursion== | ==Mutual recursion== | ||

==Tail recursion== | ==Tail recursion== |

## Revision as of 15:23, 4 June 2014

**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.