Scheme Programming 2

Scheme Programming 2

By ynori7 | 7554 Reads |

0     0

Okay, the primary goal in this article will be recursion and iteration with Scheme, and this article assumes that you have either read my scheme programming 1 article or that you have some background knowledge. Also, I forgot to mention in my last article that to put comments in Scheme, you lead your comment with a semicolon (;).

(note: ! means factorial, if you don’t know what that is, google it)

RECURSION: So I’ll start with a simple recursive procedure to find factorials. In recursive procedures, you first need to find two things: 1.) Base Case (simplest form of the problem). For example: 0!=1 2.) Recurrence Relation. Example: n!= n*(n-1)!

i apologize for the poor tabbing:

(define (fact n) (if (= n 0) ;this is our base case 1 ;if the base case is true, the procedure will return a one (* (fact (- n 1)) n) ;else the procedure will call itself up with n-1 ) ) So, (fact 3) will return 6. Let’s walk through it now. The key difference between iteration and recursion is that recursion needs to keep all of its calls in memory because it needs to come back to perform a calculation. So let’s look at this one in depth:

When you start, you call up (fact 3), which will result in 3*(fact 2), and (fact 2) is 2*(fact 1), and (fact 1) is 1*(fact 0), so once it reaches the 0, it has reached the base case which the procedure has a value for. So we end up with 112*3=6.

Activation records (stack tower): -(fact 0) -(fact 1) -(fact 2) -(fact 3) -scheme -op system

ITERATION: In iterative procedures, you need to keep track of three things:

1. Starting state
2. Terminating Criteria
3. Progress To keep things simple, I’m going to use the example of factorials again:

(define (factIter n progress partial) ;note that partial is used to keep track of the answer so far (if (= progress n) ;terminating criteria partial ;if the procedure is done, it will return the current answer (factIter n (+ progress 1) (* partial (+ progress 1) ) ) ;here’s your recursive call ) )

While there is a recursive call in the iterative solution, there is a difference. The difference is that the iterative method does not require the interpreter to keep all the method calls in memory since it doesn’t have to come back to do any calculations. Another name for the iterative procedure is ‘tail-recursive’ because the recursive call is the very last thing that is done in the procedure. (recall that in the recursive method the last thing done was the multiplication procedure, not the recursive call)

Since the interpreter doesn’t need to keep track of each method call, the new call can just overwrite the old one in the stack tower, so it will look like this:

-(fact 3) each call to factiter will just overwrite this one with the new call -scheme -op system

Iterative methods will probably run faster since the stack takes up less space and the computer doesn’t have to trace down the stack, but recursive procedures are still valuable. Some problems are just naturally solved recursively such as tree methods and Fibonacci sequences.