help understanding simple recursion

[philV]

I am long time programmer wanting to learn LISP (Clojure), watching the 1986 MIT class on the "Structure and Interpretation of Computer Programs" on youtube. 23 minutes 56 seconds into the lecture 1B ;; https://www.youtube.com/watch?v=dlbMuv-jix8

He gives a scheme recursive program to add 2 numbers, any insight would be appreciated!

Scheme version:

Code: Select all

(DEFINE (+ X Y)
   (IF (= X 0)
     Y
     (1+ (+ (-1+ X) Y))))


(I've translated to Clojure and added some print statements).

Code: Select all

(defn z [x y]
  (if (= x 0)
    (do (println "x is zero x: " x " y: " y)
      y)
    (do (println "else x: " x " y: " y)
      (inc (z (dec x) y)))))

here is the output:

Code: Select all

user> (z 4 9)
else x:  4  y:  9
else x:  3  y:  9
else x:  2  y:  9
else x:  1  y:  9
x is zero x:  0  y:  9
13


This I do not understand: the code says (= x 0) then y. When x is 0 y is 9 not 13!

[David Mullen]

Repeatedly printing X and Y doesn't reveal the whole process, whereas explicit nesting might make things clearer. The call

Code: Select all

(z 4 9)

can be re-expressed, via the function definition, as:

Code: Select all

(inc (z (dec 4) 9))

Evaluating the innermost form, this becomes:

Code: Select all

(inc (z 3 9))

Rewriting the call to Z, like we did before, we have:

Code: Select all

(inc (inc (z (dec 3) 9)))

And so on—manually evaluating the innermost form every time:

Code: Select all

   (inc (inc (z 2 9)))
=> (inc (inc (inc (z (dec 2) 9))))
=> (inc (inc (inc (z 1 9))))
=> (inc (inc (inc (inc (z (dec 1) 9)))))
=> (inc (inc (inc (inc (z 0 9)))))
=> (inc (inc (inc (inc 9))))
=> (inc (inc (inc 10)))
=> (inc (inc 11))
=> (inc 12)
=> 13

[philV]

Thanks for replying! I understand your walk through of the recursion, it is obviously correct, but seems quite counter-intuitive.

At some point state is (inc (inc (inc (inc (z 0 9))))) and then the "If" resolves to y, which seemed to me to be the culmination and the answer is 9! Since the other branch of the "if" will never again be reached it appears to me to it would therefore be of no further interest. But in fact the evaluation of that unreachable branch does continue as you show below. Both branches of the "If" are resolved to a primitive even though one is unreachable from the code!