CS1101S

Recitation 1: Recursion, 3D Vision

23 August 2012

Martin Henz

Fibonacci numbers

Leonardo Pisano Fibonacci, 12th century, was interested in the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the previous two

Computing Fibonacci numbers: Tree recursion

Recall:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n - 2) + fib(n - 1), if n > 1

function fib(n) {
    return n <= 1 ? n 
                  : fib(n - 1) + fib(n - 2);
}

Computing Fibonacci numbers: Iterative recursion

function f(n, k, f_k_minus_2, f_k_minus_1) {
    return (k > n) ? f_k_minus_1
                   : f(n,
		       k + 1,
		       f_k_minus_1,
		       f_k_minus_2 + f_k_minus_1);
}

f(6,2,0,1));

Time: linearly proportional to n

Space: constant in Scheme, linearly proportional to n in JavaScript

Factorial

Consider factorial function

n ! = n * (n - 1) * (n - 2) * ... * 1

Grouping and rewriting, we get:

n ! = n * (n - 1) !    if n > 1
    = 1                if n === 1

Factorial: Linear recursion

Grouping and rewriting, we get:

n ! = n * (n - 1) !    if n > 1
    = 1                if n === 1

function factorial(n) {
   return n===1 ? 1 : n * factorial(n-1);
}

Recursive Process

factorial(4)

4 * factorial(3)

4 * (3 * factorial(2))

4 * (3 * (2 * factorial(1)))

4 * (3 * (2 * 1))

4 * (3 * 2)

4 * 6

24

Note the build-up of pending operations.

Can we build an iterative version of factorial?

Idea: apply the scheme used in the iterative version of Fibonacci