CS1101S

Lecture 3: Recursion

12 August 2012

Martin Henz

Already awake?

	      
function mystery(x) {
    return x * mystery(x - 1);
};

mystery(5);

What is the result?

How will it end?

function mystery(x){ return x * mystery(x - 1);};
mystery(5);

5 * mystery(4);

5 * 4 * mystery(3);

5 * 4 * 3 * mystery(2);

5 * 4 * 3 * 2 * mystery(1);

5 * 4 * 3 * 2 * 1 * mystery(0);

5 * 4 * 3 * 2 * 1 * 0 * mystery(-1);

The moral of the story?

Computers will follow orders precisely.

We have no choice but to precisely describe how a computational process should be executed.

Back to the elements of programming

Primitives, combination, abstraction

What makes a good abstraction?

What makes a good abstraction?

(1) One that makes it more natural the think about tasks and subtasks.

Example:

Houses → Bricks ?

Houses → Walls → Bricks !

"Divide and Conquer"

What makes a good programming abstraction?

(1) One that makes it more natural the think about tasks and subtasks.

Program → Primitives ?

program → Procedures → Primitives !

"Divide and Conquer"

What makes a good abstraction?

(2) One that makes programs easier to read and understand.

Example 1:

	      
function beside(p1, p2) {
    return quarter_turn_right(stack(quarter_turn_left(p2),
                                    quarter_turn_left(p1)
                                   )
                             );
}

What makes a good abstraction?

(2) One that makes programs easier to read and understand.

Example 2:

function repeat_pattern(n, pat, pic) {
    if (n === 0) {
        return pic;
    } else {
        return pat(repeat_pattern(n-1, pat, pic));
    }
}

What makes a good abstraction?

(3) One that captures common patterns.

Example:

var my_cross = 
   stack(beside(quarter_turn_right(rcross_bb),
                turn_upside_down(rcross_bb)),
         beside(rcross_bb,
                quarter_turn_left(rcross_bb)));

function make_cross(p) {
    return stack(beside(quarter_turn_right(p),
                        turn_upside_down(p)),
                 beside(p,
                        quarter_turn_left(p)));
}

What makes a good abstraction?

(4) One that allows for code reuse.

Example:

var pi = 3.141592653589793;
function square(x) {
    return x * x;
}
function circle_area_from_radius(r) {
    return pi * square(r);
}
function circle_area_from_diameter(d) {
    return circle_area_from_radius(d / 2);
}

What makes a good abstraction?

(5) One that hides irrelevant details.

Example:

function persian(n, pic) {
    function besiden(n) {
        return quarter_turn_left(
                    stackn(n,
                           quarter_turn_right(pic)));
    return ...besiden;
}

What makes a good abstraction?

(6) One that separates specification from implementation.

Example:

function square(x) { return x * x; }

function double(x) { return x + x; }
function square(x) { 
    return Math.exp(double(Math.log(x)));
}

Why would we want to implement the same function in different ways?

What makes a good abstraction?

(7) One that makes debugging easier

Example:

function hypotenuse(a, b) {
    return Math.sqrt((a + a) * (b + b));
};

What makes a good abstraction?

(6) One that makes debugging easier

Example:

function sum_of_squares(a, b) {
    return square(x) * square(y);
}
function square(x) {
    return x + x;
}
function hypotenuse(a, b) {
    return Math.sqrt(sum_of_squares(a,b));
};

Variable scope

var x = 10;

function square(x) {
    return x * x;
}

function addx(y) {
    return y + x;
}

Variable scope

var pi = 3.141592653589793;
function circle_area_from_radius(r) {
    var pi = 22 / 7;
    return pi * square(r);
}

Which pi?

Variable scope

function hypotenuse(a, b) {
    function sum_of_squares() {
        return square(a) + square(b);
    }
    return Math.sqrt(sum_of_squares());
};

(or indeed...)

function hypotenuse(a, b) {
    function sum_of_squares() {
        return square(a) + square(b);
    }
    return Math.sqrt(sum_of_squares());
};

function hypotenuse(a, b) {
    var sum_of_squares = square(a) + square(b);
    return Math.sqrt(sum_of_squares);
};

JavaScript's scoping rules

(1) Variables are declared using var and using function.

JavaScript's scoping rules

(2) The scope of a var declaration is the closest surrounding function definition, or the top-level, if there is none.

JavaScript's scoping rules

(3) The scope of the formal parameters of a function definition is the body of the function.

JavaScript's scoping rules

(4) A variable occurrence refers to the closest surrounding declaration.

Conditional statements and expressions

function abs(x) {
    if (x >= 0) {
        return x;
    } else {
        return -x;
    }
}

function abs(x) {
    return (x >= 0) ? x : -x;
}

Boolean operator ||

a || b

stands for

a ? true : b

Boolean operator &&

a && b

stands for

a ? b : false;

Recursion

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

Translating to JavaScript

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.

Choosing the right solution

We have seen 53 different solutions to the persian Sidequest 2.1. Many are correct.

How to choose the best program?

Abstraction: Division of tasks, readability, common patterns etc

Performance

Choosing the right solution: Performance

Performance is measured with respect to two criteria:

• Time: how long does the program run
• Space: how much memory do we need to run the program

Time

Number of operations linearly proportional to n

factorial(4)

4 * factorial(3)

4 * (3 * factorial(2))

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

4 * (3 * (2 * 1))

4 * (3 * 2)

4 * 6

24

Space

Amount of space also linearly proportional to n

factorial(4)

4 * factorial(3)

4 * (3 * factorial(2))

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

4 * (3 * (2 * 1))

4 * (3 * 2)

4 * 6

24

Recursion Revisited

function stackn(n, pic) {
    return (n === 1) ? pic
                     : stack_frac(1/n, pic, stackn(n - 1, pic));
    }
}

Solution for n is computed using solution for n - 1.

Solution for n - 1 is computed using solution for n - 2, etc.

...until we reach a case that we can solve trivially.

Recursion Revisited

function stackn(n, pic) {
    return (n === 1) ? pic
                     : stack_frac(1/n, pic, stackn(n - 1, pic));
    }
}

1. Figure out a base case that we can solve trivially
2. Assume that you know how to solve the problem for n - 1. How can we solve the problem for n ?

Another example: 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

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: let's talk about that later

Computing Fibonacci numbers: Second way

It is known that

So one way of computing fib(n) is to simply compute the formula.

Time: ?

Space: ?

Computing Fibonacci numbers: Third way

Recall:

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

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

Tree recursion for Fibonacci numbers: Time

• Number of leaves in recursion tree is fib(n + 1)
• Due to formula we can conclude that the time is exponential in n

Tree recursion for Fibonacci numbers: Space

• At any time computing the tree, we need to remember the path to the current node
• Depth of tree grows linearly with n
• Space consumption grows linearly with n

Mutual recursion: Ping Pong

function ping(n) {
    if (n === 0) {
        return n;
    } else {
        return pong(n - 1);
    }
}
function pong(n) {
    if (n === 0) {
        return n;
    } else {
        return ping(n - 1);
    }
}

Fibonacci numbers revisited

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: let's talk about that now

Fibonacci numbers revisited

f(6, 2    , 0, 1    )
f(6, 3    , 1, 1    )
f(6, 4    , 1, 2    )
f(6, 5    , 2, 3    )
f(6, 6,   , 3, 5    )
f(6, 7,   , 5, 8    )
8  

Iterative process

• Number of steps linearly proportional to n
• Space requirement: ideally constant
• No deferred operations
• All relevant information is contained in variables

Iterative processes and programming languages

• Some languages guarantee constant space consumption for iterative processes
• One such language: Scheme
• JavaScript is not such a language
• In JavaScript every recursive function takes space proportional to the depth of the recursion

Summary

• Abstraction techniques
• Cost: time and space
• Linear recursion
• Tree recursion
• Mutual recursion
• Iterative processes