Recursive and iterative processes

Let’s consider the following code in Scheme:

#lang racket
(define (add-deferred x)
(if (eq? x 0) 0 (+ x (add-deferred (- x 1)))))

(add-deferred 3)
;(add-deferred 3)                   =
;(3 + (add-deferred 2))             =
;(3 + (2 + (add-deferred 1)))       =
;(3 + (2 + (1 + (add-deferred 0)))) =
;(3 + (2 + (1 + 0))) ## evaluate now

(define (add-iter x acc)
(if (eq? x 0) acc (add-iter (- x 1) (+ acc x))))

(add-iter 3 0)
;(add-iter 3 0) = ## evaluate
;(add-iter 2 3) = ## evaluate
;(add-iter 1 5) = ## evaluate
;(add-iter 0 6) = 9

And in C:

#include <stdio.h>

int add(int x) {
if (x == 0) {
return 0;
}

return x + add(x - 1);
}

int add_iter(int x, int acc) {
if (x == 0) {
return acc;
}

return add_iter(x - 1, acc + x);
}

int main() {
printf("%d\n", add(3));
printf("%d\n", add_iter(3, 0));
}

And then this quote from SICP:

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while.
The implementation of Scheme does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

Now since C doesn’t have tail call optimization, both calls actually produce a recursive process, that is the stack frame size grows with each call, while with Scheme the stack grows only in the case of a non-iterative process.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s