; Do not confuse a recursive PROCEDURE with a recursive PROCESS! ; ; A recursive PROCEDURE: ; * Has at least one recursive call ; * Has at least one base case ; * Can be a recursive process or an iterative process ; * Given the choice, the iterative process is almost always better ; A recursive PROCESS: ; * Has an operation that must wait until recursive calls complete ; * (See figure 1.3 from section 1.2.1 of SICP) ; An iterative PROCESS: ; * Is really a loop ; * Typically has one extra variable to keep track of state ; * Tends to be much more efficient ; * "Tail recursion" --> "Iterative process" ; Examples ; Code for counting recursive calls (define numCalls 0) (define (reset) (set! numCalls 0)) ; Recursive process example ; Correct mathematically, O(n) time and O(n) space (define (expt b n) (set! numCalls (+ numCalls 1)) (cond ((= n 0) 1) ; b^0 = 1 (else (* b (expt b (- n 1)))))) ; The * operator must wait