Revision of 1.2.1 Linear Recursion and Iteration from 11 July 2009 - 10:03pm

The revisions let you track differences between multiple versions of a post.

Printer-friendly versionPrinter-friendly version


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)
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      (+ (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 5n2.


Clojure version of iterative factorial

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

(defn factorial [n]
  (fact-iter 1 1 n))
(defn fact-iter [product counter max-count]
  (if (> counter max-count)
    (recur (* counter product)
                (+ counter 1)


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


1.2.1 Linear Recursion and Iteration | SICP in Clojure

Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my
newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you
would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy
reading your blog and I look forward to your new updates.

1.2.1 Linear Recursion and Iteration | SICP in Clojure

Coach Briefcase sale

What a funny blog! I really 1.2.1 Linear Recursion and Iteration | SICP in Clojure loved watching this funny video with my family unit as well as along with my colleagues.
Coach Briefcase sale

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options