CS1101S

Lecture 5: Recursion (continued), Higher-order Functions

29 August 2012

Martin Henz

Overview

• Leader board!
• Some admin + words of advice
• More examples of recursion
• Higher-order functions
• (Order of growth; time and space: Recitation!)

Leader board

Let's take a look!

Some Administration

Robot Project Groups

Groups of 3 or 4

Send email to Avenger Wang Sha wangshasg@gmail.com by 28/9
(end of midterm break)

Students who do not have a group will be randomly assigned

Forum Participation

Leads to Experience Points

Grading policy

• Relevance of post for classes / missions
• Effort put into writing
• Impact: Help provided, discussions generated
• Frequency

Current Affairs

Think, then code

Less is more

It's a marathon, not a sprint

Roadmap So Far

Overview

• ...
• More examples of recursion
  • Towers of Hanoi
  • Change
  • Exponentiation (review)
• Higher-order functions

First Example: Towers of Hanoi

• Given: tower of disks in increasing size
• The rule: Never put a larger disk on top of a smaller one
• How to move a tower of disks from A to B, using C?

In JediScript (Week 3)

function move_tower(size, from, to, extra) {
    if (size === 0) {
        return true;
    } else {
        move_tower(size - 1, from, extra, to);
        alert("move from " + from + " to " + to);
        return move_tower(size-1, extra, to, from);
    }
}
move_tower(3, "A", "B", "C");

In JediScript (Week 4)

function move_tower(size, from, to, extra) {
    if (size === 0) {
        ;
    } else {
        move_tower(size - 1, from, extra, to);
        alert("move from " + from + " to " + to);
        move_tower(size - 1, extra, to, from);
    }
}
move_tower(3, "A", "B", "C");

A function that does not return anything, returns undefined.

Excursion: How to read BNF

JediScript Week 4

Second example: Change

• Given: Different kinds of coins (unlimited supply)
• Given: Amount of money in cents
• Wanted: number of ways to change amount into coins

highest_denom

function highest_denom(kinds_of_coins) {
    switch (kinds_of_coins) {
        case 1: return  5; break; 
        case 2: return 10; break; 
        case 3: return 20; break; 
        case 4: return 50; break; 
        default: return 0;
    }
}

Idea in JediScript

function cc(amount, kinds_of_coins) {
    if ... /* base cases */
    else {
        return cc(amount, kinds_of_coins - 1)
               +
               cc(amount 
                  - 
                  highest_denom(kinds_of_coins),
                  kinds_of_coins)
    }
}

Adding base cases

function cc(amount, kinds_of_coins) {
    if (amount === 0) {
        return 1;
    } else if (amount < 0 || 
               kinds_of_coins === 0) {
        return 0;
    } else {
        return cc(amount, kinds_of_coins - 1)
               +
               cc(amount 
                  - 
                  highest_denom(kinds_of_coins),
                  kinds_of_coins)
    }
}

Third example: Power function: Recursive process

function power(b, e) {
    return (e === 0) ? 1 : b * power(b, e-1);
}

Power function: Iterative process

function power(b, e) {
    function power_iter(b, count, product) {
        return (count === 0) 
               ? product 
               : power_iter(b, count - 1,
                            b * product);
    }
    return power_iter(b, e, 1);
}

Fast Power function

function fast_power(b, e) {
    if (e === 0) {
        return 1;
    } else if (is_even(e)) {
        return fast_power(b * b, e / 2);
    } else {
        return b * fast_power(b, e - 1);
    } 
}

Homework: Fast Power function, iterative

• Time: O(log n)
• Space: O(log n) in JediScript, O(1) in Scheme
• More on time and space, order of growth in recitation

New topic today: Higher-order programming

• Variables revisited
• Iterative power revisited
• Passing functions
• Returning functions
• Putting it all together

Variables hold intermediate values

Compute: f(x,y) = x(1+xy)² + y(1-y) + (1+xy)(1-y)

function f(x, y) {
    var a = 1 + x * y;
    var b = 1 - y;
    return x * square(a) + y * b + a * b;
}
f(2, 3);

Variables revisited

function f(x) {
    var y = x + 1;
    return y * y;
}
f(5); alert("something"); f(7);

Passing Functions to Functions

function f(g, x) {
    return g(x);
}
f( function(y) { 
       return y + 1;
   },
   7
 );

Iterative power revisited

function power(b, e) {
    function power_iter(b, count, product) {
        return (count === 0) 
               ? product 
               : power_iter(b, count - 1,
                            b * product);
    }
    return power_iter(b, e, 1);
}

Iterative power revisited

function power(b, e) {
    function power_iter(count, product) {
        return (count === 0) 
               ? product 
               : power_iter(b, count - 1,
                            b * product);
    }
    return power_iter(e, 1);
}

Passing Functions to Functions

function f(g, x) {
    return g(g(x));
}
f( function(y) { 
       return y + 1;
   },
   7
 );

Passing Functions to Functions

var z = 1;
function f(g) {
    return g(z);
}
f( function(y) { 
       return y + z;
   }
 );

Variable Scope

function f(g) {
    var z = 4;
    return g(z);
}
f( function(y) { 
       var z = 2;
       return y + z;
   }
 );

Returning Functions from Functions

function f(x) {
    return function(y) { 
               return x + y;
           };
}
var g = f(4);
g(6);

Returning Functions from Functions

function f(x) {
    return function(y) { 
               return x + y;
           };
}
( f(4) )(6);

Returning Functions from Functions

function f(x) {
    return function(y) { 
               return x + y;
           };
}
var g1 = f(1);
var g2 = f(2);
g1(10);
g2(20);

Look at this

function sum_numbers(a, b) {
    return (a > b) ? 0 : a + sum_numbers(a + 1, b);
}

...and this this

function sum_cubes(a, b) {
    return (a > b) 
           ? 1 
           : cube(a) + sum_cubes(a + 1, b);
}
function cube(x) {
    return x * x * x;
}

...and computing Π

function frac_sum(a, b) {
    return (a > b) ? 0
                   : 1 / (a * (a + 2))
                     +
                     frac_sum(a + 4, b);
}
frac_sum(1,30) * 8;

Common pattern

function sum(a, b) {
    return (a > b) ? 0
                   : "compute value with a"
                     +
                     f("next value from a", b);
}

In JediScript

function sum(term, a, next, b) {
    return (a > b) ? 0
                   : term(a)
                     +
                     sum(term, next(a), next, b);
}

Applying sum

function sum(term, a, next, b) {
    return (a > b) ? 0
                   : term(a)
                     +
                     sum(term, next(a), next, b);
}
function sum_cubes(a, b) {
    return sum(cube, a, function(x) { return x + 1; }, b);
}

Applying sum

function sum(term, a, next, b) {
    return (a > b) ? 0
                   : term(a)
                     +
                     sum(term, next(a), next, b);
}
function sum_integers(a, b) {
    return sum(function(x) { return x; }, 
               a, 
               function(x) { return x + 1; }, 
               b);
}

Applying sum

function frac_sum(a, b) {
    return sum(function(x) { 1 / (x * (x + 2)),
               a, 
               function(x) { return x + 4; }, 
               b);
}
frac_sum(1,30) * 8;

Important Ideas

• Recursion is an elegant pattern of problem solving
• Invariant can guarantee correctness
• Functions can be passed to functions
• Functions can be returned from functions
• Functions carry with them an environment
• Higher-order functions are extremely useful
  ...and fun!