06 - Recursion in Scheme.pdf

Exercise The function for a parabola: y = ax^2 + bx + c Complete the following function definition: (define parabola (lambda (x)...)) 1 CSCI 3137 - Principles of Programming Languages 06...

Exercise The function for a parabola: y = ax^2 + bx + c Complete the following function definition: (define parabola (lambda (x)...)) 1 CSCI 3137 - Principles of Programming Languages 06 - Recursion in Scheme 2  Functional Programming and Recursion Iterative structures are problematic in Functional Programming. Generally, iteration involves updating some loop variable. If nothing changed from iteration to iteration, a loop would never terminate. From a FP perspective updating loop variables is a side-effect. (Ick.) Luckily, we know that all loops can be replaced with recursion. 3  Lets Review Recursion Define a function. Establish one or more base cases. Base cases tell us when to stop. Establish one or more recursive cases. Recursive cases are where the function calls itself with different parameters getting us closer to a base case Call that function. 4  Exercise Recall the Factorial Function: n! n! = 1 if n == 0 n! = n*(n-1)! if n > 0 Complete the following function definition: (define factorial (lambda (n)...)) 5  Recursion’s Achilles’ Heel As part of Assignment 05 how many of you tried: (factorial 1000) What happenend? StackOverflowError 6  Recursion’s Achilles’ Heel Consider how the stack behaves when evaluating (factorial 1000) Each recursive call requires its own stack frame What is the last thing the recursive case in the factorial function does? 7  Tail Recursion When the last thing a recursive subroutine does is call itself we call that tail-recursion Tail recursion is useful because it means that the recursive call can actually re-use the same stack frame Essentially, the language treats the tail recursive subroutine as a loop where the parameters are loop variables 8  Tail Recursion The factorial function doesn’t exhibit tail-recursion That forces each recursive call to create a stack frame Thus the stack overflow for large n 9  Exercise Can we rewrite the factorial function to create tail-recursion? Perhaps by writing a recursive helper function? Complete the following function definition: (define fact-helper (lambda (n m fm)...)) (define factorial (lambda (n) (if (< n 0) 1 (fact-helper n 1 1)))) 10  Is There a Better Way? Separate helper functions tend to clutter up the namespace Nobody wants to call fact-helper directly Is there a better way? Short Answer: yes Long Answer: Time for a short detour 11  Local Binding: let (let ((name1 expr1) (name2 expr2)...) expression) Evaluates expression with the given names bound to the corresponding expressions Note: these variables must be independent. expr2 cannot reference name1 12  Exercise Complete the following definition of the fibonacci function using let (define fibonacci (lambda (n) (if (< n 2) n (let ((fn-1...) (fn-2...))...)))) 13  Named let Computing Fibonacci numbers naively involves a lot of repeated work. In an imperative language we would replace the recursion with iteration. We can achieve the same thing in Scheme using named-let Named-let adds a name before the list of bindings And that name can be used inside the expression to recursively evalulate the expression with different bindings 14  Named let (let name ((name1 expr1) (name2 expr2)...) expression) Besides just binding namei to expri We also bind name to (lambda (name1 name2...) expression) This means that expression can apply name to different arguments recursively Note that name is only bound inside expression so it doesn’t clutter the namespace 15  Fibonacci Revisited (define fibonacci (lambda (n) (if (< n 2) n (let f ((m 2) (fm 1) (fm-1 1)) (if (= m n) fm (f (+ m 1) (+ fm fm-1) fm)))))) If n < 2 then (fibonacci n) is equal to n otherwise Starting at m = 2 where f_m is 1 and f_m-1 is also 1 When we reach m = n return f_m Otherwise compute the next m, f_m, and f_m-1 16  Exercise Lets use named-let to do for factorial what we did for fibonacci Complete the following function definition: (define factorial (lambda (n)...)) 17  Exercise The Padovan Sequence is a sequence of integers defined by: P(0) = P(1) = P(2) = 1 and the recurrence relation P(n) = P(n-2) + P(n-3) Complete the following function definition: (define padovan (lambda (n)...)) 18