Skip to content

Instantly share code, notes, and snippets.

@mohanrajendran
Created July 11, 2014 00:28
Show Gist options
  • Save mohanrajendran/a722b75069e6a1dc85e8 to your computer and use it in GitHub Desktop.
Save mohanrajendran/a722b75069e6a1dc85e8 to your computer and use it in GitHub Desktop.
SICP Exercise 1.9

Expansion of (+ 4 5) using first definition

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

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

As can be seen, there is a chain of deferred inc operations as function is evaluated. Thus, this process is recursive.

Another way to determine that this process is recursive is by observing that the recursive call is nested within another function.

Expansion of (+ 4 5) using second definition

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

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

In this case, there are no deferred operations. The function evaluates exactly to another instance of itself. Thus, this process is iterative.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment