Notes for Lab 2

Notes for Lab 2
[Main Page]

Table of Contents
A. Recursion
1. Definition
2. Base Case
3. Reduction Step
B. Processes
1. Recursive Processes
2. Iterative Processes
C. Writing Recursive Procedures
1. General Format for Recursive Processes
2. General Format for Iterative Processes
D. New Special Forms - Cond
1. Format
2. Evaluation

A. Recursion

1. Definition

We define a recursive procedure or function to be one that calls itself and therefore "recurses". A working recursive procedure must have the following two main components:

2. Base Case

The base case of a recursive procedure is the halting point for the recursion. In other words, at some point the recursive procedure needs to halt, and we call the situation in which it does so, the base case. We think of the base case as the situation in which no further recursion is needed to complete the task we set out to do.

For example, suppose that we are writing a recursive procedure to compute the factorial of a number. We know that n! = n * (n-1) * (n-2) * ..., but 0! = 1. Logically, we can compute n! as n * (n-1)!, but we need to stop eventually. Thus, it makes sense to set 0! = 1 as our base case.

3. Reduction Step

Since recursive procedures call themselves, we use this when computing otherwise complicated functions (or to do other tasks) by having the recursive call act on a simpler set of inputs.

In the previous example, we were computing the factorial function. Since n! = n * (n-1)! for n > 0, we can use this as our reduction step. We compute (n-1)! and multiply by n to get n!. To compute (n-1)!, we find (n-2)! and so on until we hit the base case, which is 0! = 1.

B. Processes

We define a process to be a little different from a procedure or function. A procedure or function is a block of code, while a process is intangible and describes the manner in which a procedure or function operates. Thus, a recursive procedure or function is simply a block of code that calls itself, while we define a recursive process somewhat differently. (see below)

1. Recursive Processes

A recursive process is a process in which there are deferred operations. What we mean by this is that after the base case is reached in a recursive procedure, there are still operations to be carried out before a final result can be returned.

In the above factorial example, when computing n!, we have to wait for (n-1)! to be computed before we can multiply by n to get the result. Similarly, for (n-1)!, we have to wait for (n-2)! before we can multiply by (n-1). Thus, even after we have reached the base case of 0! = 1, we still have to multiply by 1 to get 1!, we have to multiply 1! by 2 to get 2!, etc. all the way back up to n. Since these operations can't be carried out before we reach the base case, they are deferred, and we have a recursive process.

2. Iterative Processes

Iterative processes act in a different manner than recursive processes. Whereas recursive processes have deferred operations that compute the result after the base case is reached, an iterative process does the computation as it goes along so that when the base case is reached, a result can be returned immediately without any deferred operations.

The most common way that you will see and use of writing iterative processes is through the use of a helper procedure. The helper procedure will usually contain more arguments than the original function since it needs to store temporary values as well as the final result as computed so far.

In the factorial example, we can write an iterative version that computed factorial as we go along. The way to do this is to store the current product. Since multiplication is commutative (a*b = b*a), we can compute n! as (((n * (n-1)) * (n-2)) * (n-3)) ... We can do this by introducing another variable in the helper function that stores the current product. At each step we multiply the current product by the number argument. When the base case is reached, we will have computed the final result already, so we can just return the value and not worry about any deferred operations.

C. Writing Recursive Procedures

These are only guidelines to writing recursive procedures. For complicated functions and tasks, you will most likely need to alter these templates to accomodate your specific problem.

1. General Format for Recursive Processes

(define f
  (lambda (<args>)
    (if <base case condition>
      <base case result>
      (<deferred op> <deferred op args> (f <reduced problem args>))
    )
  )
)

2. General Format for Iterative Processes

(define f
  (lambda (<args>)
    (define (helper (<args> <result variable>))
      (if <base case condition>
        <result variable>
        (helper (<reduced problem args> <new result>))
      )
    )
  (helper (<args>) <base case result>)   )
)

D. New Special Forms - Cond

1. Format for Cond expressions

Cond is a special form, so it needs to follow a specific format or the substitution model will fail:
(cond
(<test> <expression>)
(<test> <expression>)
...
)

2. Evaluation for Cond expressions

The evaluation order for cond is to evaluate each of the <test> clauses in order. If a <test> clause evaluates to true, then the corresponding <expression> clause is evaluated and returned. The last <test> clause can be else, which will always evaluate to true. If none of the <test> clauses evaluate to true, the cond expression result is undefined.