help understanding simple recursion

You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.
Post Reply
philV
Posts: 2
Joined: Fri May 13, 2016 10:12 am

help understanding simple recursion

Post by philV » Fri May 13, 2016 10:49 am

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
Posts: 78
Joined: Mon Dec 01, 2014 12:29 pm
Contact:

Re: help understanding simple recursion

Post by David Mullen » Sat May 14, 2016 2:13 pm

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
Posts: 2
Joined: Fri May 13, 2016 10:12 am

Re: help understanding simple recursion

Post by philV » Sat May 14, 2016 4:17 pm

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!

Post Reply