Topic: Recursion

[Keith™]

Run this bit of code and note the order of the values returned

Code: [Select]


(defun Count (inc stop)
  (setq X inc)
  (princ "\n")
  (princ X)
  (if (/= x stop)
   (Count (1+ inc) stop)
  )
  (princ "\n")
  (princ X)
)


What you get is
1
2
3
4
5
6
7
8
9
10
10
10
10
10
10
10
10
10
10

The reason is because the first call to Count is still executing while the second, third etc. run.

Imagine it like this ...
count[1] calls count[2] calls count[3] ..... calls count[10] .....
count[10] completes execution
count[9] completes
count[8] completes
count[7] completes
.....
count[1] completes

As you each of the recursive counts finish BEFORE the calling instance.

I hope I have not confused you even more ....

[JohnK]

wow! Very good explination Stig.

[JohnK]

Ok Daron, I took this right out of the Scheme book (So I dont screw up anynmore. --I guess i should have looked harder before I gave you those functions. ) But anyways here is a Recursive Procedure using a Recursive process.

Code: [Select]

(defun factorial (n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

(factorial 6)
> 720

[daron]

That is way too much. That is cool, but I think my head is spinning more now than before.
I tried something simple:
(factorial 3)
> 6

Question: What is the original value of factorial?

[JohnK]

I dont understand your question so ill give you these links.

What is a Factorial:
http://mathforum.org/library/drmath/view/57594.html

Table of Factorials 1! - 30!
http://mathforum.org/library/drmath/sets/select/dm_factorial_list.html

[daron]

Okay, that helped a bit, but this helped even more with understanding what factorial is. My question though, was dealing with how a recursive procedure works. When the code gets to the part where it calls itself, what is the value of itself, that it doesn't crash on the first go around.

[JohnK]

Fill in the values as it goes thru. Like this:
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

[daron]

I think I see the answer. Since the procedure doesn't complete, as Keith stated, until it has stepped through the process the given number of times, it isn't calcing anything until it's through, then steps backwards through the process as you've shown to complete the function. Woohoo! I finally understand. Now I just need to find something to write one.