General form of recursive algorithms test base case. recursive case (define fact (lambda(n) (if( n 1) test for base case base case (n (fact(-n 1)); recursive case base case: smallest(non-decomposable) problem recursive case: larger(decomposable) problem sept.8.2003 16.41016.413 Intro to Scheme Avoiding Recursion In factorial, was pending for each level recursion. Consumes stack space How can we avoid that? (define(fact n let loop(n n)(answer 1)) f(=n1) answer (loop(n 1)(answer n)) sept.8,2003 16.410/16.413 Intro. to scheme 9/ General form of recursive algorithms , base case, recursive case ( ) ) 1 : • smallest (non-decomposable) problem recursive case: larger (decomposable) problem 17 ))) • base case Sept. 8, 2003 16.410 16.413 Intro. to Scheme • test define fact (lambda (n (if (= n 1 ; test for base case ; base case (* n (fact (- n 1)) ; recursive case Avoiding Recursion • In factorial, * was pending for each level of (define (fact n) (let loop ((n n) (answer 1)) 18 recursion. Consumes stack space. – How can we avoid that? (if (= n 1) answer (loop (- n 1) (* answer n))))) Sept. 8, 2003 16.410/16.413 Intro. to Scheme 9