We begin by considering the factorial function, defined by .

There are many ways to compute factorials. One way is to make use of
the observation that `n`! is equal to `n` times (`n` - 1)! for
any positive integer `n`:

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,
this observation translates directly into a procedure:

```
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
```

We can use the substitution model of section Section 1.1.5 to watch this procedure in action computing 6!, as shown in figure 1.3.

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`.

Once again, we can recast our description as a procedure for computing factorials:[29]

```
(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)))
```

As before, we can use the substitution model to visualize the process of computing 6!, as shown in figure 1.4.

Compare the two processes. From one point of view, they seem hardly
different at all. Both compute the same mathematical function on the
same domain, and each requires a number of steps proportional to *n*
to compute `n`!. Indeed, both processes even carry out the same
sequence of multiplications, obtaining the same sequence of partial
products. On the other hand, when we consider the “shapes” of the
two processes, we find that they evolve quite differently.

`n`!, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with

`n`(is proportional to

`n`), just like the number of steps. Such a process is called a linear recursive process.

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. In computing `n`!, the number of steps required grows linearly with `n`. Such a process is
called a linear iterative process.

The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables. Not so with the recursive process. In this case there is some additional “hidden” information, maintained by the interpreter and not contained in the program variables, which indicates “where the process is” in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.[30]

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
we shall consider in chapter 5 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.[31]

In a real program we would probably use the block structure introduced in the last section to hide the definition of `fact-iter`

:

```
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
```

We avoided doing this here so as to minimize the number of things to think about at once. [back]

Exercises

## Exercise 1.9

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures `inc`

, which increments its argument by 1, and `dec`

, which decrements its argument by 1.

```
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
```

Using the substitution model, illustrate the process generated by each procedure in evaluating `(+ 4 5)`

. Are these processes iterative or recursive?

## Exercise 1.10

The following procedure computes a mathematical function called Ackermann’s function.

```
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
```

What are the values of the following expressions?

```
(A 1 10)
(A 2 4)
(A 3 3)
```

Consider the following procedures, where `A`

is the procedure defined above:

```
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))
```

Give concise mathematical definitions for the functions computed by the procedures `f`

, `g`

, and `h`

for positive integer values of `n`. For example, `(k n)`

computes 5`n`^{2}.

## Comments

## Clojure version of iterative factorial

Clojure doesn’t have tail recursion due to limitations with the JVM so you have to explicitly use ‘recur’:

## TXPFqcqogM

Very true! Makes a change to see soomnee spell it out like that. :)

## http://www.rateamateapp.com

http://xn—ghq332m.com/bbs/forum.php?mod=viewthread&tid=151917 http://jwc.dongyueweb.com/forum/forum.php?mod=viewthread&tid=672752 http://bbs.storberry.com.cn/forum.php?mod=viewthread&tid=906494 http://www.cslife.org/forum.php?mod=viewthread&tid=597431 http://three-body.com/forum.php?mod=viewthread&tid=256136 http://mail.eachina.org.cn:8080/upload/forum.php?mod=viewthread&tid=2213906 http://longmen.6macau.com/forum.php?mod=viewthread&tid=229887 http://yoyaer.com/forum.php?mod=viewthread&tid=1043581 http://dz.aqualem.com/forum.php?mod=viewthread&tid=313319 http://bbs.xarg.com.cn/forum.php?mod=viewthread&tid=597811 http://imperiusdamian.x10host.com/wiki/index.php/User:Djvl44pg#camisetas… http://bbs.77w.net/forum.php?mod=viewthread&tid=616353 http://uctest.ucweb.com:81/discuzx2/forum.php?mod=viewthread&tid=109105 http://www.51nitian.com/thread-727899-1-1.html http://zk.duerain.com/sns/forum.php?mod=viewthread&tid=595836 http://www.345wan.com/bbs/forum.php?mod=viewthread&tid=126564 http://bbs.fzycw.net/forum.php?mod=viewthread&tid=806921 http://www.c-kf.com/bbs/forum.php?mod=viewthread&tid=186046 http://igoviva.com/forum.php?mod=viewthread&tid=50830 http://mmwk.cn:8088/1/tzb/forum.php?mod=viewthread&tid=511320 http://by78.com/forum.php?mod=viewthread&tid=399816 http://www.bjsfedu.com/forum.php?mod=viewthread&tid=353594 http://www.pingguo4.com/forum.php?mod=viewthread&tid=396585 http://xa.hengzhibs.com/forum.php?mod=viewthread&tid=116279 http://bbs.51mainet.com/forum.php?mod=viewthread&tid=26621 http://www.yoyaer.com/forum.php?mod=viewthread&tid=1043588 http://bbs.xjeep.cn/forum.php?mod=viewthread&tid=515426 http://www.yxqnlxx.cn/Review.asp?NewsID=38 http://www.roomie.com.cn/forum.php?mod=viewthread&tid=67105 http://26w.com.cn/forum.php?mod=viewthread&tid=371814 http://bbs.ymxx.mhedu.sh.cn/forum.php?mod=viewthread&tid=11788489 http://www.islesofdoom.com/wiki/index.php?title=User:Nuaa04sa#Cheap_Socc… http://h.znovels.com/space.php?uid=357314&do=blog&id=2373347 http://lnkjoy.com/bbs/forum.php?mod=viewthread&tid=947889 http://www.buji8.com/forum.php?mod=viewthread&tid=1380707 http://jetmotoboat.com/forum.php?mod=viewthread&tid=514364 http://bbs.weifangcn.com/thread-434507-1-1.html http://vibebbs.com/forum.php?mod=viewthread&tid=970446 http://118.244.203.38/thread-626701-1-1.html http://www.wx0.net/forum.php?mod=viewthread&tid=91784 http://www.face-pic.org/blog/26738/football-shirts-uk-380f6h6-41020/ http://www.islesofdoom.com/wiki/index.php?title=User:WdcoxwgN#Soccer_Jer… http://www.zoom51.com/forum.php?mod=viewthread&tid=89699 http://www.jlxshx.com/Review.asp?NewsID=433 http://ncut.me/forum.php?mod=viewthread&tid=335719 http://www.myokez.tw/forum.php?mod=viewthread&tid=1342970 http://bbs.51xingtai.com/forum.php?mod=viewthread&tid=802962 http://www.51liuxue.ca/forum.php?mod=viewthread&tid=515294 http://0769yjl.com/forum.php?mod=viewthread&tid=738016 http://raegquit.com/wiki/index.php?title=User:YpreuuBc#camiseta_barcelon… http://www.528club.com/forum.php?mod=viewthread&tid=2439474 http://club.xiangqinba.com/home/space.php?uid=406610&do=blog&id=3534105 http://110.90.120.57:88/forum.php?mod=viewthread&tid=1543730 http://xbzhaopin.com/forum.php?mod=viewthread&tid=1303794 http://www.hebidianjing.com/web/thread-237317-1-1.html http://www.njhdwj.com/read.php?tid=242469 http://jk578.com/read.php?tid=3437215 http://www.rosemeadchamber.org/index.php?do=/blog/add/ http://www.9xchem.com/bbs/home/space.php?uid=149714&do=blog&id=1051894 http://zaojiao.siai.co/forum.php?mod=viewthread&tid=65252 http://www.amiella.com/forum.php?mod=viewthread&tid=212673 http://www.dtstudyclub.com/index.php?do=/blog/add/ http://www.nss184xx.com/Review.asp?NewsID=497 http://goldfishhome.gicp.net/uchome/space.php?uid=306223&do=blog&id=1407478 http://philipsokolov.com/phpbb/viewtopic.php?p=436422#436422 http://www.nnro-pran.ru/forum/viewtopic.php?p=42262#42262 http://bbs.eeu.cn/read-htm-tid-416927.html http://humaraadab.com/wiki/index.php?title=User:IyuhghvN#Soccer_Jerseys_… http://olveczkylab.fas.harvard.edu/OpCon/index.php?title=User%3AG80bsyb0… http://shamanita.org/wiki/index.php?title=User:ArhphkxN#Cheap_Football_S…

http://www.rateamateapp.com http://www.rateamateapp.com

## Post new comment