Recursion and Iteration are two types of evaluation methods in scheme language.
Lets explain this with the help of some examples. First of all consider the case of finding factorial of a number defined by:
n! = n(n-1)(n-2).......3.2.1
Now lets consider the two ways to compute the result. The first one is to consider that n! is equal to n times (n - 1)! for any positive integer n:
n! = n[(n-1)(n-2).......3.2.1] = n.(n-1)!
Thus, we can compute n! by computing (n - 1)! and multiplying the result by n. If we add the stipulation that 1! is equal to 1,we can define the procedure as folows:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Using the above defined procedure, the evaluation process for computing 3! can be picturised as follows:
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 1))
(* 3 2)
6
Now let's take a different perspective on computing factorials. We could describe a rule for computing n! by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until we reach n. More formally, we maintain a running product, together with a counter that counts from 1 up to n. We can describe the computation by saying that the counter and the product simultaneously change from one step to the next according to the rule
product
counter · product
counter counter + 1
and stipulating that n! is the value of the product when the counter exceeds n.
So using this above described method, we can compute the factorial of n using the following procedure:
(define (factorial n)
(fact-iter 1 1 n)) (define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
We can use the substitution model to visualize the process of computing 3!, as shown in figure given below:
(factorial 3)
(factorial 1 1 3)
(factorial 1 2 3)
(factorial 2 3 3)
(factorial 6 4 3)
6
Considering the two methods, the shapes of the evaluation process figure is different for recursion and iterative process. The first figure reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on.
By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.
These are some of the main differences between linear recursive and iterative evaluation. Please refer here to read more about the topic with more examples.
Lets explain this with the help of some examples. First of all consider the case of finding factorial of a number defined by:
n! = n(n-1)(n-2).......3.2.1
Now lets consider the two ways to compute the result. The first one is to consider that n! is equal to n times (n - 1)! for any positive integer n:
n! = n[(n-1)(n-2).......3.2.1] = n.(n-1)!
Thus, we can compute n! by computing (n - 1)! and multiplying the result by n. If we add the stipulation that 1! is equal to 1,we can define the procedure as folows:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Using the above defined procedure, the evaluation process for computing 3! can be picturised as follows:
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 1))
(* 3 2)
6
Now let's take a different perspective on computing factorials. We could describe a rule for computing n! by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until we reach n. More formally, we maintain a running product, together with a counter that counts from 1 up to n. We can describe the computation by saying that the counter and the product simultaneously change from one step to the next according to the rule
product
counter · product counter
counter + 1and stipulating that n! is the value of the product when the counter exceeds n.
So using this above described method, we can compute the factorial of n using the following procedure:
(define (factorial n)
(fact-iter 1 1 n)) (define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
We can use the substitution model to visualize the process of computing 3!, as shown in figure given below:
(factorial 3)
(factorial 1 1 3)
(factorial 1 2 3)
(factorial 2 3 3)
(factorial 6 4 3)
6
Considering the two methods, the shapes of the evaluation process figure is different for recursion and iterative process. The first figure reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on.
By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.
These are some of the main differences between linear recursive and iterative evaluation. Please refer here to read more about the topic with more examples.
