Use the "debug" button DrScheme to debug programs, and also to understand how recursive functions are operating
;; general form (define (func x) (if end-test end-value (augmenting-function augmenting-value (func reduced-x))))Factorial is the classic example:
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))Many Scheme functions operate on lists, so we often see an important special case of augmenting recursion where our augmenting function is cons and our base case is the empty list. Notice that because we are using cons, we are actually constructing a brand new list and returning it. In other words, we are not changing the original list.
(define (double-each s) (if (null? s) '() (cons (* 2 (car s)) (double-each (cdr s)))))Our base value (the value returned when we reach the base case) isn't always ():
(define (my-append x y) (if (null? x) y (cons (car x) (my-append (cdr x) y))))A final important kind of recursion over lists is the class of reducing functions, because they reduce a list of elements to a single element.
;; sum the elements of a list (define (sumlist x) (if (null? x) 0 (+ (car x) (sumlist (cdr x)))))
;; general form: (define (func x) (cond (end-test-1 end-value-1) (end-test-2 end-value-2) (else (func reduced-x)))) ;; example: are all elements of a list positive? (define (all-positive x) (cond ((null? x) #t) ((<= (car x) 0) #f) (else (all-positive (cdr x))))) ;; (all-positive '(3 5 6)) => #t ;; (all-positive '(3 5 -6)) => #fSome tail recursive functions will have more than one argument. All but one of the arguments are passed along unaltered.
;; example: member: (define (my-member e x) (cond ((null? x) #f) ((equal? e (car x)) #t) (else (my-member e (cdr x)))))A less commonly seen form is single-test tail recursion.
Scheme compilers handle tail recursion very efficiently, as efficiently as a program that just uses loops instead of recursion. (In particular, tail recursive functions don't use stack space for every recursive call.)
(define (factorial n) (acc-factorial n 1)) ;; auxiliary function that takes an additional parameter (the accumulator, ;; i.e. the result computed so far) (define (acc-factorial n sofar) (if (zero? n) sofar (acc-factorial (- n 1) (* sofar n))))Mini-exercise: Define a tail recursive version of a sumlist function to find the sum of the numbers in a list. (Hint: you can define an auxiliary function if needed.)
;; test whether two lists have the same length (define (same-length x y) (cond ((and (null? x) (null? y)) #t) ((null? x) #f) ((null? y) #f) (else (same-length (cdr x) (cdr y))))) ;; do these two objects have the same shape? (define (same-shape x y) (cond ((and (pair? x) (pair? y)) (and (same-shape (car x) (car y)) (same-shape (cdr x) (cdr y)))) ((or (pair? x) (pair? y)) #f) (else #t)))Mini-exercise: Define a function addlists that takes two lists of numbers, and adds the corresponding elements of each. Ignore extra elements if one of the lists is longer than the other. For example
(addlists '(1 2 3) '(10 11 12)) => '(11 13 15)
(define (func x) (cond (end-test end-value) (aug-test (augmenting-function augmenting-value (func reduced-x))) (else (func reduced-x)))) ;; example: remove all non-positive numbers from a list (define (positive-numbers x) (cond ((null? x) '()) ((> (car x) 0) (cons (car x) (positive-numbers (cdr x)))) (else (positive-numbers (cdr x)))))Mini-exercise: Scheme has a builtin function filter that takes a predicate and a list s, and returns a new list consisting of all elements of s for which the predicate is true. For example
(filter even? '(1 2 3 4 5)) => (2 4)Define your own version myfilter.
;; variation on list-consing recursion (define (insert x s) (cond ((null? s) (list x)) ((< x (car s)) (cons x s)) (else (cons (car s) (insert x (cdr s)))))) ;; augmenting recursion (define (isort s) (if (null? s) '() (insert (car s) (isort (cdr s)))))
Map is a built in Scheme function that takes a function and a list as an argument, and returns the list that results by applying that function to every element of the list.
(map function list) ;; general form (map null? '(3 () () 5)) => (() T T ()) (map round '(3 3.3 4.6 5)) => (3 3 5 5) (map cdr '((1 2) (3 4) (5 6))) => ((2) (4) (6))
(map (lambda (x) (* 2 x)) '(3 4 5)) ;; the right way to define addN-to-list (define (addN-to-list alist n) (map (lambda (x) (+ n x)) alist))Please note that in the addN-to-list function, the body of the lambda function can refer to the variable n, which is in the lexical scope of the lambda expression.
map can also be used with functions that take more than one argument. Examples:
(map + '(1 2 3) '(10 11 12)) => (11 13 15) (map (lambda (x y) (list x y)) '(a b c) '(j k l)) => ((a j) (b k) (c l))
(define (my-map func alist) (if (null? alist) '() (cons (func (car alist)) (my-map func (cdr alist)))))
(define (addN-to-list alist n) (my-map (lambda (x) (+ n x)) alist))When the lambda expression is used in my-map, it needs to know where to look up the variable name n. It can get the right value for n, because it retains its lexical environment.
As an example, let's define a simple function test:
(define (test x) (+ x 1))Evaluating (test 10) gives 11.
However, if we evaluate
(let ((test (lambda (x) (* x 2))) (test 10))we get 20 -- within the let, test is rebound to a different function.