Recursive function behavior in c++
I know basic definition of recursive function.....but i want to know its impact on memory?? Why it is not chosen over loop or iteration?
C++ does not mandate tail call optimization, so recursive functions that can trivially be converted to loops may still take up space linear in the call depth (storing the frame).
Additionally, C/C++ does not necessarily detect stack overflow, so that's another problem with potentially deep calls.
EDITED to have more qualified language ("necessarily")
Some people seem hung up over the fact that specific compilers such as gcc and clang perform tail call optimization and/or stack overflow detection. The point is, if it is not mandated, then it is unsafe. For example, gcc only performs tail call optimization at -O2, -O3 and -Os. So, if the program depends on tail call optimization being performed, the program will mysteriously die when someone compiles without an optimization flag (on gcc).
If it is good programming practice, then, by all means, they can continue to write programs that depend on compiler flags. Or ones that depend on compilers. Optimization not optional.
It's usually not chosen for one of two reasons:
- the coder doesn't understand recursion (in particular, tail-end optimisation); and
- it can be expensive on stack space.
Although the standard has nothing to say about stack space, it's often a limited resource prone to overflow.
For example, this is a bad recursive function:
def addTwoPositiveNumbers (a,b): if b == 0: return a return addTwoPositiveNumbers (a+1,b-1)
(unless it can do that tail end optimisation). That's because it can theoretically use a lot of stack levels, for example when b = 1,000,000,000, it will use a billion stack frames.
On the other hand a binary search is not too bad since it removes half the search space with each level of recursion. So even if you had a billion entries, that would only be log21,000,000,000 or 30 stack levels.
Having listed the reasons why I think people avoid it, I should say that I use it quite a bit and you should realise that many problems are naturally expressed better as a recursive solution. The code is cleaner and more readable. For that reason alone, it should be a part of your arsenal.
You can always rewrite recursion with an iterative operation - the question becomes one of readability/easiness of implementation. And for quite a few problems, recursion leads to simpler algorithm (e.g. most stuff related to graph/tree).
As far as memory goes: in a language like C or C++, every function call needs to push its arguments to the calling stack. This stack has a limited size (having a 100-long chain of calls is almost always ok - 1000000 almost certainly not). The exact limitation are highly system dependent.
More high level languages, especially functional ones, have "tricks" to enable for stack which seem "infinite" in some cases (tail calls, which are pretty common cases). Such languages often guarantees the optimization, called Tail Call Optimization (TCO), which enable for elegant code in cases where recursion makes sense.