Topic: Recursion HowTo

[Mark]

Anyone have time to explain how a recursion function works?

[David Bethel]

Simply put it is when a program calls back on itself until the desired results or tests are met

http://theswamp.org/phpBB2/viewtopic.php?t=2481

There is an example of recusrion in this thread

(cnt) calls back to itself;

Code: [Select]

(defun cnt (item lst num)
  (cond ((null lst) (cons item num))
        ((not (member item lst))(cons item num))
        ((cnt item (cdr (member item lst)) (1+ num)))
  )
)


Not always the most efficient way in terms of computing speed with large computaions, but it can be elegant code.  -David

[JohnK]

Nice David, I like that.

Heres one off the top of my head. (Im gonna type this in the reply box so the formatting might not be on.)

Code: [Select]


(defun make10 (n)
  ;; Make a nuber at least 10
    (if (>= n 10)
  ;; If the number already is ten or above then...
        n
  ;; Then return it. Otherwise incriment the number
  ;; and send it back thru again.
        (make10 (1+ n))))

...See ya!

[JohnK]

Oh i thought i should mention that these are examples of Recursive procedures (wherein they refer to themselves) using itterative process (wherein there are no other values/process to be evaluated in the stack besides 'it'.).

{That sounds confusing but i think you get the point. *lol*}

[MP]

This one is for the noobs ...

Think about the following (run the snips if you wish to confirm) and try to explain the output:

Code: [Select]

(defun fact1 ( x )
    (print
        (if (< x 2)
            x
            (* x (fact1 (1- x)))
        )
    )
)

(fact1 5)

1
2
6
24
120 120

(defun fact2 ( x )
    (print x)
    (if (< x 2)
        x
        (* x (fact2 (1- x)))
    )
)

(fact2 5)

5
4
3
2
1 120

[JohnK]

Oho thats a very good example of a procedure that is not a Recursive procedure using a itterative process. *lol*

[MP]

Eh? This would be an iterative version of a factorial function:

Code: [Select]

(defun fact ( x / result )
    (repeat (1- (setq result x))
        (setq result
            (*  result
                (setq x (1- x))
            )    
        )
    )
)

[SMadsen]

Mark, are you looking for a more indepth discussion of recursion, rather than examples? How values are pushed and popped and things like that?

[Mark]

Yes I am Stig. Some of us have a hard time grasping this technique(?) of programming. Even though, as David pointed out, it may not be the most efficient way of doing things in some cases, (IMO) it should still be understood by all wishing to learn how to program.

[daron]

Well, while I still don't have a full grasp of it yet, I do have some things I'd like to point out that might not jump right out at a newbie. Then again, recursion is not for the newbie lisper (programmer) by any strecth. Here goes: First, just like defining a function or lambda expression, you need to supply as many arguments as are being called for. Ex.

Code: [Select]

(defun test (x y z / a b c)
)
(mapcar '(lambda (x) (convert x to "z")) newlist)
(defun recurse (sslist)
 (recurse (External{sslist}Function))
)

Some people know that a defun can pull information in from external functions. If they don't, they should now. That would be what the first parsed example would do.

The lambda expression's X value uses whatever would be in newlist from mapcar to process the information contained in it. Mapcar Lambda is quite similar in nature to foreach as I understand it. It takes each element in a list, one item at a time and does what is required until it reaches the end of the list.

I've brought all that up because I feel without that knowledge, it would blow more than one circuit for anybody to understand recursion. As is shown by all the examples above, the recursive process requires just as many arguments inside the recurring procedure as it does when it's being called. Now, as I understand it, what is taking place is every time the procedure calls itself, it takes whatever information it has stored, processes itself again and stores that value with the other stored value(s) until it reaches the end of a given cycle. The warning flag with recursion is that if you don't supply some way for the procedure to stop itself, it will literally go on forever if you have enough memory in your system.

Now, I would like to ask some questions. How does recursion relate to append? Does it? How does recursion give you any return value when it's done, since after it processes all that it can, it proceeds to nil out each value from the last to the first? This is where I'm stuck. How do I keep all the values it stores after the procedure is complete?

[Keith™]

Recursion, in its simplest form performs a function or group of functions on a single object

example

Code: [Select]


(defun decrement ( value )
 (if (> value -1)
 (progn
 (princ "\n")
 (princ value)
 (decrement (1- value))
 )
)
)


Note that there is no code after the recursion call. If there was it would not be executed until the final recursion is done.

You are correct in that it calls itself continually unless you have a means by which it will exit the recursion. To examine this, remove the "if" portion of the above code.
Incedently the stack limit is reaced with this code at around 19995 recursions

[David Bethel]

Add this 2 Se7en's code:

Code: [Select]

(trace make10)


Then run:

Code: [Select]

(make10 2)

And the results look like this:

Code: [Select]


Command: (make10 2)

Entering (MAKE10 2)
  Entering (MAKE10 3)
    Entering (MAKE10 4)
      Entering (MAKE10 5)
        Entering (MAKE10 6)
          Entering (MAKE10 7)
            Entering (MAKE10 8)
              Entering (MAKE10 9)
                Entering (MAKE10 10)
                Result:  10
              Result:  10
            Result:  10
          Result:  10
        Result:  10
      Result:  10
    Result:  10
  Result:  10
Result:  10
10



My guess in cpu useage terms, the program pushes each result until termination and then has to pop off everything to clear the stack.

And as Keith pointed out, if you make an error in the code, you cannot make infinite loop using recursion.  You get the following error ( A2K ):
Hard error occurred ***
internal stack limit reached (simulated)

R12 & 13 just says:
AutoLISP stack overflow

In the old days you could adjust the Autolisp STACK and HEAP valves.  I don't beleive that is the case today.

-David

[whdjr]

Incedently the stack limit is reached with this code at around 19995 recursions

Whew!  Let's hpoe we don't need that today.

[Keith™]

Well, the sad truth is that while 19995 does seem like a high number, it is frequently passed in numeric calculations, even in lisp routines ... only we aren't running 19995 routines at once....

[JohnK]

Here is a great explination of the diff types of Recurstion.
LINK

[SMadsen]

Daron, I agree it's pretty confusing how a recursive function can deliver a result other than the input when it reverses the process upon exit.
Consider the MAKE10 function above. If you set a breakpoint and add n to the watch window, it's obvious that n is decrementing to the original input as the recursion backtraces. But it has already returned a value of 10. The important thing - as Keith mentions - is not to place any call after the recursive call because that would then be the result.

Try rewrite the MAKE10 function to this:

Code: [Select]

(defun make10 (n)
  (if (>= n 10) n
    (make10 (1+ n))
  )
  n
)

This is perhaps the most common error to make in a recursive function. It will drag its own backtrace along and return the original input - to itself.

(make10 6) -> 6

In trace window:

Code: [Select]

Entering (MAKE10 6)
  Entering (MAKE10 7)
    Entering (MAKE10 8)
      Entering (MAKE10 9)
        Entering (MAKE10 10)
        Result:  10
      Result:  9
    Result:  8
  Result:  7
Result:  6

The explicit return value will cause the function to receive whatever it pops off the stack. In this example it will return the value of n to itself - thus decrementing the value while popping it off.
When it's not superceded by another call - like in the original MAKE10 - there is nothing to return but n=10.

As for APPEND, it is by nature a recursive function due to how a list is represented with CONS pairs. I doubt it is written as a recursion in the ARX module rather than an iterative one but it is pretty easy to write your own APPEND as a recursive function:

Code: [Select]

(defun myAppend (a b)
  (cond ((null a) b)
        ((cons (car a) (myAppend (cdr a) b)))
  )
)

[SMadsen]

Here is a great explination of the diff types of Recurstion.
LINK

There ya go. Excellent find, John!

[MP]

That's a very nice start on a tutorial Stig. I look forward to your forthcoming posts in this thread.

Alas, if I only had the time, this is one of favorite topics. If there's anything left to discuss I'll try this weekend coming up, otherwise it's just short posts for me.

PS - that's a very fine book John.

[JohnK]

I love that book! It explains sooo muh.

Good post Stig.

[daron]

Yes, thank you Stig. You have a very good command of the English language. I hope I'm not the only recursion newbie learning anything on this subject. Thanks for bringing it up Mark.

[Mark]

I hope I'm not the only recursion newbie learning anything on this subject. Thanks for bringing it up Mark.

*cough* why do you think I brought it up.  

Thanks to all for helping Daron and myself understand recursion.  I think the trace command is one of the best ways to understand how these gems work.

[daron]

I thought you had a pretty good understanding of it, Mark.