Will my recursive procedure cause a stack overflow?
It depends on the kind of recursive procedure you have designed, depending on the problem, most naive recusions can be converted to tail-calls(in tail call optimised 'TCO' languages), which allows a recursion to run in constant memory space without using mutation or other stateful things.
In scheme, 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 constant memory, which is equal to the space needed to store the call to loop on the stack. this procedure is not a function, it uses mutation to iterate (its also a recursion ;) but..).
In scheme, two recursions:
(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 a normal recursion, and is very much functional, there is no state change, instead, the memory use grows as new lexical closures are created with each fact-1
call, eventually exhausting the stack. It 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
Whereas Fact-2 is recursive, but in tail form, so instead of building the stack, and collapsing the calls at the base 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
Which is equivalent to making fact-1 into an interative process, but without mutation, as values are passed forward, instead of assignment. Notice that each call still produces a new lexical closure, but since the function doesnt return to the original caller, but to the original callers stack location, the compiler can discard the previous closures instead of having them nesting inside of each other, re-binding the variables at each level of recursion.
So where should I use recursion vs iteration
That depends entirely on both the process to be designed and the language used. If your language does not support TCO, then you will need to only use shallow recursions, and write looping(recursive or iterative) procedures in a stateful manner. If you do have TCO, then it could be best to use recursion, or tail-calls, or stateful things, or a combination of them. Not all recursive procedures can be written in tail form, and not all iterative processes can be written as a recursion. If you are concerned about memory usage, and are wanting deep recursions, you must use Tail-calls.
NOTE:
Some of you may have noticed, but the first procedure is actually a tail call too, but the example still illustrates the point of a normal iteration doing stateful! things, and running in constant maximum memory regardless for all valid inputs.