Scheme Recursion/Lambda Lab

 

It would be wise to type in and evaluate each of the function/constructs/expression in this lab before attempting to complete the lab assignments.

 

Recursion

Recursion is a term used to describe a procedure that calls itself, directly or indirectly. In Scheme, simple program repetition/iteration can be achieved via recursion by having a function call itself. Most programs are tail recursive, where the recursive call is the last action that occurs. In other words, there is no need to return for further execution of the ith iteration of the function after the recursive call to the (i + 1) iteration.

Note: Most functional languages implement tail/end recursion as efficiently as iteration.


tail/end recursion	g(n)	=	0		if n <= 1 {base condition}
				=	g(n-1)		if n > 1

not tail recursion	g(n)	=	0		if n <= 1 {base condition}
				=	2 * g(n-1)	if n > 1

So, tail/end recursion returns a constant or just the result of a recursive call. The implementation of tail/end recursion is shown below:


while not (base condition) do
	{body of loop}

Most imperative languages do not implement tail/end recursion as efficiently as iteration. This would be theoretically possible as a compile-time optimization. But since recursion is less central to imperative languages there is less need for this optimization.

There are two required elements for recursion:

    1. There must be a halting case.
    2. There must be a recursive call that merges toward the halting case.

Recursion is often best understood through examples.

THE COOKIE MONSTER: simple tail recursion

(define (cookie-monster n) ; (name parameter)

(if (= n 0) ; halting case

(begin

(newline)

(display "Do you have any more cookies?"))

(begin

(newline)

(display "Munch Munch Cookie #: ")

(display n)

(cookie-monster (- n 1))))) ; tail/end recursion

It is common for the number of recursive calls to be contingent on a parameter. In this example, the cookie-monster repeats based on the single parameter n. The cookie-monster can also be solved iteratively, but the process favors the recursive approach because each action is a subset of the first.

The following code determines the length of a list recursively:

(define (list-length lst)

(cond

((null? lst) 0)

(else (+ 1 (list-length (cdr lst))))))

The call (list-length '(a b c d)) will yield a 4.

The call (list-length '(a b (c d))) will yield a 3.

 

An iterative construct

The syntax for a do loop is as follows:

(do ((<variable> <initial-value> <update>) ...)

(<termination-test> <expression> ...)

<statement> ...)

The following code determines the length of a list iteratively:

(define (list-length lst)

(do ((len 0 (+ len 1))) ; initial cond and update

((null? lst) len) ; termination test and return value

(set! lst (cdr lst)))) ; loop body

The following code sums the number between 1 and n iteratively:

(do ((i 1 (+ i 1)) ; initial cond and update

(sum 0)) ; initial cond and NO update

((> i n) sum) ; termination test and return value

(set! sum (+ sum i))) ; loop body

 

Back to Recursion

Let (fact X) represent a procedure call to factorial with an argument of X. Then the following shows how (fact 4) is executed.

(fact 4) = 4 *	(fact 3)
			(fact 3) = 3 *	(fact 2)
						(fact 2) = 2 *	(fact 1)
									(fact 1) = 1
						(fact 2) = 2 * 1
			(fact 3) = 3 * 2
(fact 4)	= 4 * 6
		= 24

One implementation of the famous factorial function:

(define (factorial X)

(cond

((equal? X 0) 1)

(else (* X (factorial (- X 1))))))

An implementation of reversing a list:

(define (rverse lst)

(cond

((null? lst) '())

(else (append (rverse (cdr lst)) (cons (car lst) '())))))

You might try replacing (cons (car lst) '()) with (list (car lst)) .

Lambda

In Scheme, lambda is a syntactic form that evaluates to a procedure.

(lambda <parameters> <expression>...)

Where <parameters> are variables and <expression> is the function body. Lambda can be thought of as a synonym for "function."

f(x) = x * x

(lambda (x) (* x x))

Note the replacement of lambda (x) for f(x).

A simple example of how to use lambda:

(define (add x y) (+ x y))

or

(define add (lambda (x y) (+ x y)))

The following is a recursive procedure that removes an item from a list.

(define remove

(lambda (lst item)

(cond

((null? lst) '())

((equal? item (car lst)) (cdr lst))

(else (cons (car lst) (remove (cdr lst) item))))))

The call (remove '(a b c) 'b) will yield the list (a c).

The call (remove '(1 2 3) '3) will yield the list (1 2).

 

LAB ASSIGNMENTS:

1. Fibonacci Numbers: The Fibonacci numbers are the series of numbers: 1 1 2 3 5 8 13 21 34... The first two numbers in the series are 1 and any following number in the series is determined by adding the two previous numbers. Therefore, the third number is the sum of the first two numbers 1 + 1 = 2; the fourth number is the sum of the second and third numbers 1 + 2 = 3; the fifth number is the sum of the third and fourth numbers 2 + 3 = 5, etc. You are to write a recursive procedure, fib, to find the nth Fibonacci number. This procedure should receive the index of the number to be found and then calculate this number. For example, (fib 6) should yield the sixth Fibonacci number and should return the number 8.

2. Write a recursive procedure find-a that receives a list and returns the position of the first occurrence of the letter a. The first position in the list is the position 0 therefore, calling find-a on the list (b c d a e a) will return a 3. The helping procedure you write (called first-a) does the actual recursion. One approach is to have a variable that holds the position number to be defined in the find-a procedure and passed to the helping procedure first-a.

Hint: print-loop below is the helping procedure to print-numbers also defined below.

(define (print-loop n max)

(cond (( > ( * n n) max))

(else (display n)

(print-loop (+ 1 n) max )))

)

(define (print-numbers max)

(print-loop 1 max)

)

 

Turn in a hardcopy of each answer as well as a disk with the programs clearly marked.