[Help] Limit of recursive

Hi all ^^

I've tried to use recursive with a huge list, and find out that it has limit, but i don't know what exactly number ?

See in this Ex with LM:mAssoc :

(defun LM:mAssoc ( key lst / pair )
   (if (setq pair (assoc key lst))
       (cons (cdr pair) (LM:mAssoc key (cdr (member pair lst))))
   )
)
(defun test (num / lst)(setq i 0)(repeat num (setq lst (cons  (cons 1 (setq i (1+ i))) lst))))

Then test :

Command: (setq l1 (LM:Massoc 1 (test 10000)) dump 0)

0 => ok

 

Command: (setq l1 (LM:Massoc 1 (test 34000)) dump 0)

Hard error occurred ***

internal stack limit reached (simulated)

Command: (setq l1 (LM:Massoc 1 (test 32000)) dump 0)

Hard error occurred ***

internal stack limit reached (simulated)

Command: (setq l1 (LM:Massoc 1 (test 30000)) dump 0)

Hard error occurred ***

internal stack limit reached (simulated)

Please help me. Thank all ^^

Not sure ... but it seems the largest value in your code which doesn't produce the error is 19996.

You could of course use an iterative MAssoc:

;; Multiple assoc, by Lee Mac
(defun MAssoc (key lst / pair return)
 (while (setq pair (assoc key lst))
   (setq return (cons (cdr pair) return)
         lst    (cdr (member pair lst))
   )
 )
 (reverse return)
)

Eg.:

Command: (length (Massoc 1 (test 1000000)))
1000000

Strangely I have another recursive MAlloc function:

(defun mAssocR1 (key lst / res)
 (if (and lst (setq res (assoc key lst)))
   (cons (cdr res) (mAssocR1 key (cdr (member res lst))))
 )
)

This gets a single value more before the error happens:

Command: (length (mAssocR1 1 (test 19997)))
19997

Command: (length (mAssocR1 1 (test 19998)))
Hard error occurred ***
internal stack limit reached (simulated)

So I guess for large lists you'd be better off going with iterative routines. To check which you'd prefer, look at this thread: http://www.cadtutor.net/forum/showthread.php?55931-mAssoc-implementations

Recursion limits used to be dependent on your hardware. Maybe it still is. -David

Recursion is always limited by the size of the stack memory it is allocated. When you run a program a 'stack' of activation records are maintained, there is one activation record for every active method - a method is 'active' if it has been called but hasn't yet returned, e.g.:

(defun _copycat ( x )
   (if (atom x)
       x
       (cons (_copycat (car x)) (_copycat (cdr x)))
   )
)

Here, the 'cons' method is still active when the recursive call is made. The activation record stores the parameters/variables and 'return address' for the method. The return address tells the interpreter where in the code to continue evaluation after the method returns.

When you call a method, such as 'cons' above, the activation record is 'pushed' onto the stack memory. When the method returns, the return address is read and the activation record is 'popped' from the stack memory.

However, now consider the case of recursion: the activation record for the 'cons' method remains on the stack when the recursive call is made; similarly, another activation record is pushed onto the stack when the next recursive call is made, and another, and another, until the recursion reaches the base case and the method returns - at which point the activation records are 'popped' from the stack at each level of the recursion.

Therefore the limiting factor is the size of the allocated stack memory, limiting how many activation records can be pushed onto the stack, and hence how many levels of recursion can be achieved.

^^ Thanks all. From now on, i will try to avoid it. App can be slow, but can't crash ^^

^^ Thanks all. From now on, i will try to avoid it. App can be slow, but can't crash ^^

On the contrary, recursion is usually far slower than iterative solutions.

Exaggerated example:

(defun fib_recurse ( n )
   (if (<= 2 n)
       (+ (fib_recurse (- n 1)) (fib_recurse (- n 2)))
       n
   )
)

(defun fib_iter ( n / a b c )
   (setq a 0 b 1 c 1)
   (repeat (- n 2) (setq a b b c c (+ a c)))
   c
)

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

   (FIB_ITER 10)........1326 / 4.21 <fastest>
   (FIB_RECURSE 10).....5585 / 1 <slowest>

So... what is the reason to use recursion somewhere if it Short, but slow and dificult to understand ? ^^

So... what is the reason to use recursion somewhere if it Short, but slow and dificult to understand ? ^^

In some cases it results in concise and elegant solutions, and for others it is almost the obvious choice, such as when processing nested lists.

In some cases it results in concise and elegant solutions, and for others it is almost the obvious choice, such as when processing nested lists.

Oh, right.. Thank you Lee. You help me like a "live dictionary" ^^