Topic: Recursion

[daron]

A few weeks ago, Se7en threw some recursive procedure's my way to help me understand them a bit more. I was looking at them today and while watching the values and setting the vlide to animate, I noticed something that I didn't realize about recursion. While in the animation, the procedure started at a user set value, variable num. That value would increase in size until the procedure got to the highest number it was designed to get to, being 10 and return the value of 10. When it reached 10 it would step backwards through the procedure and discount the value of num back to what the user defined. Why is this? Is this just a way of clearing the variable num and being recursive, it has to clear it as many times as it was called?

[JohnK]

Ill see if i can really understand what your asking and work up a demo. but for the rest of the guys, here are the proedures i gave him to look at and try to understand.

Code: [Select]

;;; A recursive procedure using an iterative process
(defun Count2Ten (num)
  (if (>= num 10)
    num
    (Count2Ten (+ 1 num))))
;;; A recursive procedure using a recursive process
(defun TwoTimesTen (num)
  (if (>= num 10)
    num
    (* (Count2Ten (+ 1 num)) 2)))

[daron]

Thanks.

[JohnK]

Oh wow. Now i understand what your asking. Hey thats cool. Im gonna run some more tests.

Run this and youll see what hes talking about.

Code: [Select]

;;; A recursive procedure using an iterative process
(defun Count2Ten (num)
  (cond
    ((>= num 10) num)
    ((princ num)(Count2Ten (+ 1 num))(princ num))))

[daron]

Now that's cool.

Check this one out.
(twotimesten 3)
4567899876548
Where'd the 8 come from?

[JohnK]

wait a min theres a mistake in the first code i posted. ...brb.

(Daron are those the exact same procedures i gave you?)

[daron]

Exactly.

[JohnK]

DAMN! Those are wrong! ...? (well the first one is alright, but the second one is wrong.)

[daron]

I was wondering about that too. What's the second one supposed to do? I'll see if I can make it happen.

[JohnK]

Sorry, I got hit with something, Ill try to explaine a little bit about my statment now.

First of all; The the second example is not really what I said it is in my header. Let me try to put it into words.

A Recursive Procedure is basicly a procedure that refers to itself.

A Recursive Process is defigned as a chain of deferred operations.

So therefore, its not really a Recursive Procedure to begin with. (For the reason that for it to get the number ten it has to call another procedure. --get it?)

[daron]

Must not, because I thought that's what it was doing. Maybe some more code would help.

[JohnK]

Code: [Select]

(defun Count2Ten (num)
  (if (>= num 10)
    num
    (Count2Ten (+ 1 num))))
Ok this procedure calles itself right? --Right.
Therefore, this procedure is a Recursive procedure (because it makes reference to itself.)

Code: [Select]

(defun TwoTimesTen (num)
   (if (= num 10)
     num
    (* 2 (Count2Ten (+ 1 num)))))
This procedure does NOT refer to itself; it calles the "count2ten" procedure. So that means that its not --by deffinition-- recursive procedure. (It calles a recursive procedure, but it isnt one itself)

[daron]

So are you saying that a recursive process has to be recursive itself while calling a recursive procedure? or am I shooting past the mark?

[JohnK]

kinda.  But your getting it. To be a "deferred chain of operations" it has to have stuff to do before it can do the stuff that is ...deferred. *poof!* --Did you just see what happened to my head? I think i pulled a muscle in my brain with that statment.

[SMadsen]

I think that the difference between the first and the second Count2Ten is an excellent example to show what recursion does, and what NOT to do in a recursive function.

A call like (setq a (count2ten 1.0)) returns 10 in the first instance and 1 in the second, even though the COND should return num when 10 is reached. I don't know if my english will suffice to explain it, but I'll give it a try.

A function that has been evaluated puts the value on the stack if further evaluations await. That way it can evaluate deeply nested functions and still keep track of the evaluation.
When a recursive function runs, it continuously puts the values that are returned from each call on the stack. Either it fills up the stack (and is caught by the interpreter) or, hopefully, it encounters a stop-value, in this case (>= num 10).

When that value is reached, it is returned to the calling function, which is the first instance of the function - or the first level. However, all levels still need to pop off the values that they put on the stack, so it starts backtracing. Unless they cause any further expressions to be evaluated during the backtrace they only pop off values till the stack is empty.

The second Count2Ten had a PRINC statement that followed the nested call. During each call to Count2Ten, it never got to that PRINC statement before calling itself. But on the backtrace it continues evaluation from the point that it stopped at on each level, which - except for the last called Count2Ten that stopped at ((>= num 10) num)) - is at the nested Count2Ten. This causes it to evaluate any following expressions left on each level and that's where the last PRINC statement comes into play. It returns the value of num while it is being pulled from the stack .. to the calling function!

The stack is last-in-first-out, so as num was incremented by each level it seems to be decrementing while backtracing (no calculation is done - it's only values taken from the stack). Finally, SETQ will recieve the value from the calling Count2Ten.


By the way, the "first" Count2Ten referred to above is

Code: [Select]

(defun Count2Ten (num)
(if (>= num 10)
num
(Count2Ten (+ 1 num))))


and the "second" is

Code: [Select]

(defun Count2Ten (num)
(cond
((>= num 10) num)
((princ num)(Count2Ten (+ 1 num))(princ num))))


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