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.