Will my recursive procedure cause stack overflows? It depends on the type of recursive procedure that you have developed, depending on the problem, most naive recursions can be converted to tail calls (in tail-optimized TCO languages), which allows recursion to work in a constant memory space without using mutations or other conditions related to the state.
In the diagram, an iterative process:
(let ((i 0) (max 10)) (let loop () (cond ((< i max) (printf "~A~N" i) (set! i (+ i 1)) (loop)) (else i))))
This procedure uses read-only memory, which is equal to the space required to store the call in a loop on the stack. this procedure is not a function, it uses a mutation for iteration (its also recursion;), but ..).
There are two recursions in the schema:
(define (fact-1 n) (cond ((eq? n 1) n) (else (* n (fact-1 (- n 1)))))) (define (fact-2 n carry) (cond ((eq? n 1) carry) (else (fact-2 (- n 1) (* carry n)))))
Fact-1 is normal recursion and very functional, there is no change in state, instead, memory usage increases when new lexical closures are created with every fact-1 call, which ultimately ends the stack. He grows like
=>(fact-1 10) ..(* 10 (fact-1 9)) ..(* 10 (* 9 (fact-1 8))) ..(* 10 (* 9 (* 8 (fact-1 7)))) .. ..... ..(* 10 (... (* 2 1) ...)) .. ..... ..(* 10 362880) =>3628800
While Fact-2 is recursive, but in a tail form, so instead of creating a stack and folding calls in the basic case, the value is passed forward, and we get this:
=>(fact-2 10 1) ..(fact-2 9 10) ..(fact-2 8 90) ..(fact-2 7 720) .. .......(fact-2 1 362880) =>3628800
This is equivalent to turning fact-1 into a process of interaction, but without mutation, because the values are passed forward instead of being assigned. Note that each call still creates a new lexical closure, but since the function does not return to the original caller, but to the original location of the caller’s stack, the compiler can discard previous locks instead of having them nested inside each other, re-bind the variables on each recursion level.
So where should I use recursion versus iteration It completely depends on the process that needs to be developed, and on the language used. If your language does not support TCO, you will need to use small recursions and write down cyclic (recursive or iterative) stateful procedures. If you have a TCO, then it is best to use recursion, or tail calls, or stateful state, or a combination of these. Not all recursive procedures can be written as tail, and not all iterative processes can be written as recursion. If you are concerned about memory usage and want deep recursions, you should use Tail-calls.
Note: Some of you may have noticed, but the first procedure is actually a tail, but the example still illustrates the point of normal iteration executing the state! things and work in constant maximum memory, regardless of all valid input data.