Fibonacci recursion -argh

Recursion is slowing me down immensely in my learning of Common Lisp. Recursion is simple, but I have a hard time visualizing the cycle flow. I tried drawing flow charts, but flow charts don't visualize accumulation very well. For me, it seems that evaluation code flow works best for understanding recursion. I think I got most of the recursion templates down, but the multiple/tree recursion is still wracking my brain. Here is the infamous code for the Fibonacci number:

(defun fibo (n)
	(cond ((equal n 0) 1)
		 ((equal n 1) 1)
		 (t (+ (fibo (- n 1)) (fibo (- n 2))))))

I am trying to figure out how lisp evaluates this program one cycle at a time and this is what I think happens:

(fibo 5)

(+ (fibo 4) (fibo 3))

(+ (+ (fibo 3) (fibo 2)) (+ (fibo 2) (fibo 1)))

(+ (+ (+ (fibo 2) 1) (+ (fibo 1) 1)) (+ (+ (fibo 1) 1) 1))
...
(+ (+ (+ (+ 1 1) 1) (+ 1 1)) (+ (+ 1 1) 1))

(+ (+ (+ 2 1) 2) (+ 2 1))

(+ (+ 3 2) 3)
...
8

I think my evaluation code is probably disorganized, but I would just be happy that my basic assumption is confirmed.

You can ask lisp what it sees,

(trace fibo)

Which will output he following now:

* (fibo 5)
  0: (FIBO 5)
    1: (FIBO 4)
      2: (FIBO 3)
        3: (FIBO 2)
          4: (FIBO 1)
          4: FIBO returned 1
          4: (FIBO 0)
          4: FIBO returned 1
        3: FIBO returned 2
        3: (FIBO 1)
        3: FIBO returned 1
      2: FIBO returned 3
      2: (FIBO 2)
        3: (FIBO 1)
        3: FIBO returned 1
        3: (FIBO 0)
        3: FIBO returned 1
      2: FIBO returned 2
    1: FIBO returned 5
    1: (FIBO 3)
      2: (FIBO 2)
        3: (FIBO 1)
        3: FIBO returned 1
        3: (FIBO 0)
        3: FIBO returned 1
      2: FIBO returned 2
      2: (FIBO 1)
      2: FIBO returned 1
    1: FIBO returned 3
  0: FIBO returned 8
8

Then just turn it off when done,

(untrace fibo)

Remember also that Common Lisp put much less emphasis on recursion than Scheme, in particular not requiring tail call optimization, so it should be used only when the data operated upon is actually recursive (usually trees).

Personally I never had problems with recursion because I never saw why calling a function from itself would be different from calling any other function. But then, I learnt about functional programming somewhat late, so I avoided the "recursion for iteration" and other magic issues. Or maybe it was exposition to mathematical induction long before I started programming. Or perhaps I don't really understand recursion, but I just don't really see what is there to understand.

Although not required by standard, CL implementations usually implement tail call optimization. E.g., SBCL, clisp (as a compiler, not interpreter), ecl (as a compiler).

I guess you are wrong about the evaluation order.

The rule is: when you call a function, only the steps inside that call are evaluated. Well, these words do not explain much, but this is what I mean:

(fibo 3)

;; is "expanded" to

(+ (fibo 2) (fibo 1)) ; (+ a b)

;; then it calculates the value of A (and forgets about B)

a: (fibo 2)
   -->
   (+ (fibo 1) (fibo 0)) ; (+ c d)

   c: (fibo 1)
       -->
       1

   d: (fibo 0)
       -->
       1

;; now that it know the values of C and D, it can calculate the value of A

a: (+ 1 1) ; (+ c d)
    -->
    2

;; only now it steps forward to the calculation of B

b: (fibo 1)
    -->
    1

;; now that it knows A and B, it can return the answer

(+ 2 1) ; (+ a b)
-->
3

Using your notation:

(fibo 3)

(+ (fibo 2) (fibo 1))

(+ (+ (fibo 1) (fibo 0)) (fibo 1))

(+ (+ 1 (fibo 0)) (fibo 1))

(+ (+ 1 1) (fibo 1))

(+ 2 (fibo 1))

(+ 2 1)

3

The call to (fibo 5) takes too much steps, which is boring to reproduce by hand, that is why I chose (fibo 3). And, exactly because it takes too much steps, this implementation of Fibonacci code is so infamous. This one is O(n):

(defun nacci (n)
  (do ((k 2 (1+ k))
       (Fk-2 1 Fk-1)
       (Fk-1 1 (+ Fk-1 Fk-2)))
      ((> k n) Fk-1)))

Thank you gugamilare. I appreciate the correction. I can see now that it works on the left main branch first. I wonder where I can find a comprehensive description of Lisp evaluation order. Perhaps the Hyperspec...

Well, I installed SBCL again after reinstalling XP for the millionth time. Finally, trace is working for me. I was using Clozure CL and it would return NIL when I trace:

? (trace fibo)
NIL
? (fibo 5)
0> Calling (FIBO 5) 
<0 FIBO returned 8
8
? 

speech impediment wrote:I can see now that it works on the left main branch first. I wonder where I can find a comprehensive description of Lisp evaluation order. Perhaps the Hyperspec...

Not surprisingly, it can be found in chapter Form Evaluation, specifically here. Not that evaluation order really matters when the forms are not side effecting.

I thought this is pretty interesting in the Hyperspec:

Although the order of evaluation of the argument subforms themselves is strictly left-to-right, it is not specified whether the definition of the operator in a function form is looked up before the evaluation of the argument subforms, after the evaluation of the argument subforms, or between the evaluation of any two argument subforms if there is more than one such argument subform. For example, the following might return 23 or 24.

(defun foo (x) (+ x 3))
(defun bar () (setf (symbol-function 'foo) #'(lambda (x) (+ x 4))))
(foo (progn (bar) 20))

I tested this code in both Clozure CL and SBCL and I got 24. It seems that these two implementations look up the definition of the operator after evaluation of the argument subforms. This is why I got confused about this code from Touretzky's book about helping functions.

(defun count-up (n) (count-up-recursively 1 n))

(defun count-up-recursively (cnt n)
	(cond ((> cnt n) nil)
			(t (cons cnt (count-up-recursively (+ cnt 1) n)))))

I just didn't understand how you can use the function count-up-recursively when it wasn't even defined yet. I was wondering why didn't he just put the count-up definition below? It seems like it doesn't matter ...or does it? I mean is it just an unformalized tradition that argument subforms are evlauted before the definition of the operator? Do you know of any implementations that evaluate things differently?

speech impediment wrote:I just didn't understand how you can use the function count-up-recursively when it wasn't even defined yet. I was wondering why didn't he just put the count-up definition below? It seems like it doesn't matter ...or does it? I mean is it just an unformalized tradition that argument subforms are evlauted before the definition of the operator? Do you know of any implementations that evaluate things differently?

That example doesn' t have anything to do with the one from Hyperspec. There is a difference between defining the function and calling it. All functions which are actually called have to be defined by the time the caller calls them, but they do not have to be defined when the called is defined. The implementation might signal a warning, but it can be resolved using with-compilation-unit.

The Hyperspec thing you mention is an edge case which doesn't actually appear in practice, since redefining global functions is extremely confusing and bad style.

Recursion is slowing me down immensely in my learning of Common Lisp. Recursion is simple, but I have a hard time visualizing the cycle flow

(IMO) The whole point of using recursion is to avoid the extra work of having to look at or manage cycle flow, and thus be able to code faster and more powerfully. You only need to figure out 2 things-how to handle the none final base cases, and how to handle the final base cases.

(defun fibo (n)
   (cond ((equal n 0) 1)
       ((equal n 1) 1)
;the above are the final base cases because they aren't calling fibo, they are returning 1
       (t (+ (fibo (- n 1)) (fibo (- n 2))))
;the above are the none final base cases
;you know they are correct because--
;; a. they are correct as a fibonaci producing function using the abstract number series n
;; b. all of your final base cases have been correctly defined
;; c. all of your none final base cases have been correctly defined 
;;you just saved a bunch of coding time by ignoring looping considerations and only considering the exact math abstractions involved with base case shortcuts
   )
)

base cases may involve atoms, lists, trees, nils, car's of trees, and/or cdr's of trees. If you want to recurse Down a pre existing tree data structure, you will usually want to recurse both the car and cdr of the tree in order to cover every branch and leaf. In the fibo example you are working with a new tree instead of recursing down a pre existing one. Then again I suppose fibo could be said to have a pre existence in the math dimension.

For more:
'the little schemer'
'ansi common lisp'

ps-here is another way to think about it
will this produce the correct result? (fibo 2)
if so, how and why?
Is there any difference between why (fibo 2) works and why (fibo n) works where n is any integer?

pps-visualizing recursion (or lambda calculus (math seen as abstractions of functions and vice versa)) on a register machine is like doing integration on an abacus, possible, but why do it? For those who insist, think about how functions, pointers and return values are stored and swapped around on the stack and between the registers.

speech impediment wrote:I thought this is pretty interesting in the Hyperspec:

Although the order of evaluation of the argument subforms themselves is strictly left-to-right, it is not specified whether the definition of the operator in a function form is looked up before the evaluation of the argument subforms, after the evaluation of the argument subforms, or between the evaluation of any two argument subforms if there is more than one such argument subform. For example, the following might return 23 or 24.

(defun foo (x) (+ x 3))
(defun bar () (setf (symbol-function 'foo) #'(lambda (x) (+ x 4))))
(foo (progn (bar) 20))

I tested this code in both Clozure CL and SBCL and I got 24. It seems that these two implementations look up the definition of the operator after evaluation of the argument subforms. This is why I got confused about this code from Touretzky's book about helping functions.

(defun count-up (n) (count-up-recursively 1 n)
)

(defun count-up-recursively (cnt n)
	(cond ((> cnt n) nil)
			(t (cons cnt (count-up-recursively (+ cnt 1) n)))
	)
)

I just didn't understand how you can use the function count-up-recursively when it wasn't even defined yet.

CL is a dynamic language. You are allowed to define functions later and even to redefine them if you like (except, perhaps, for explicitly inlined functions and ANSI functions). The hyperspec part you quoted is a clear example of that.

Once again, thank you everyone for all your time and help. I am glad that I can move forward. I hope not to be stuck again on another topic. I will probably come back when I hit object orientation.