Scheme Recursion Exercises

Straight and Iterative-style Recursions:
Remember the two techniques we used for to calculate the Triangle numbers T(N): (1 + 2 + 3 + ... + N):

straight recursion:
	(define (Tri-1 N)
		(if (= N 1) 1 
			(+ N (Tri-1 (- N 1)))))

iterative recursion:
	(define (Tri-2-helper Target Pos Sub)
		(if (= Pos Target) Sub
			(Tri-2-helper Target (+ 1 Pos) (+ Sub 1 Pos))))

	(define (Tri-2 N)
		(Tri-2-helper N 1 1))

Recursion on Lists:
Here's how we created our function MyLength(L) that returned the number of elements in a list (assuming that we didn't have access to the built-in Scheme function length):

	(define (MyLength L)
		(if (null? L) 0
			(+ 1 (MyLength (cdr L)))))
	
	(MyLength '(A (B C) D)) ;-> 3

Here's how we add up a bunch of numbers in a list:

	(define (AddNumbers L)
		(if (null? L) 0
			(+ (car L) (AddNumbers (cdr L)))))

	(AddNumbers '(12 -2 4)) ;-> 14

Here's how we create a list of N numbers in increasing order starting at 1 (assume N >= 1). Example:

	(Sequence 5)  ;-> (1 2 3 4 5)

	(define (Sequence N)
		(if (= N 1) '(1)
			(append (Sequence (- N 1)) (list N))))

Exercises:

1a) Create the function EvenSum(N) which will be given an even number greater than 0, and will add up all the even numbers between it and 0 (plus itself). So:
(EvenSum 4) ;-> (2 + 4) = 6

1b) Create the function EvenSum2(N): If you used straight recursion in 1a), then do it with iterative recursion, or vice versa.

2) Create a function similar to the Fibonacci function, but instead of adding up the previous 2 numbers, it adds up the previous 3 numbers. We'll call it the Fibonacci-acci(N) function (or FAA(N) for short). To start it off, we'll let FAA(1) = 0, FAA(2) = 1 and FAA(3) = 1. Then, we see that FAA(4) = 2, and FAA(5) = 4, etc. Do this with iterative recursion, because otherwise you'll never be able to do question 2c.
2a) Calculate FFA(20) and put the result into the comments-to-teacher
2c) Is it true that FAA(2000) is evenly divisible by 7? (again, put Yes or No in the comments-to-teacher)

3) Create the function MultNumbers(L) which will be given an non-empty list of numbers and will multiply them all together. Example:

	(MultNumbers '(2 5 8)) ;-> 80

4) We're (well, actually, you're) going to create two new versions of the factorial function.
4a) Do it with iterative recursion.
4b) Use MultNumbers.

5) Create the list function MyReverse(L) which will do the same thing as the built-in function Reverse. (Don't even think about using Reverse.) Example:

	(Reverse '(A 12 My foot)) ;-> (foot My 12 A)

6) Create the function Explode(N) which is given a non-negative number and creates a list of its digits. Example:

	(Explode 263) ;-> (2 6 3)
	(Explode 8) ;-> (8)

7) (harder) Create the function Implode(L) which will be given a non-empty list of digits, and will create the corresponding number from it. Example:

	(Implode '(2 6 3)) ;-> 263
	(Implode '(8)) ;-> 8