Fibonacci recursion -argh

Discussion of Common Lisp
speech impediment
Posts: 36
Joined: Mon May 04, 2009 5:19 pm

Fibonacci recursion -argh

Post by speech impediment » Tue Oct 20, 2009 9:05 pm

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:

Code: Select all

(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.
Last edited by speech impediment on Wed Apr 23, 2014 10:44 pm, edited 1 time in total.

billy
Posts: 8
Joined: Fri Apr 24, 2009 11:56 am

Re: Fibonacci recursion -argh

Post by billy » Tue Oct 20, 2009 10:03 pm

You can ask lisp what it sees,

Code: Select all

(trace fibo)
Which will output he following now:

Code: Select all

* (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,

Code: Select all

(untrace fibo)

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Fibonacci recursion -argh

Post by ramarren » Wed Oct 21, 2009 12:47 am

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.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: Fibonacci recursion -argh

Post by dmitry_vk » Wed Oct 21, 2009 2:02 am

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).

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Fibonacci recursion -argh

Post by gugamilare » Wed Oct 21, 2009 5:48 am

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:

Code: Select all

(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:

Code: Select all

(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):

Code: Select all

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

speech impediment
Posts: 36
Joined: Mon May 04, 2009 5:19 pm

Re: Fibonacci recursion -argh

Post by speech impediment » Wed Oct 21, 2009 8:18 pm

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:

Code: Select all

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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Fibonacci recursion -argh

Post by ramarren » Wed Oct 21, 2009 10:14 pm

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.

speech impediment
Posts: 36
Joined: Mon May 04, 2009 5:19 pm

Re: Fibonacci recursion -argh

Post by speech impediment » Fri Oct 23, 2009 8:48 am

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.

Code: Select all

(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?
Last edited by speech impediment on Wed Apr 23, 2014 10:56 pm, edited 2 times in total.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Fibonacci recursion -argh

Post by ramarren » Fri Oct 23, 2009 9:21 am

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.

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Fibonacci recursion -argh

Post by methusala » Fri Oct 23, 2009 10:31 pm

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.

Code: Select all

(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.

Post Reply