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?
1
-
For the responders: I see a bunch on "recursion sucks if not TCO", etc, but in many problems I have dealt with, the level of recursion is trivially small (and stack "allocations" are quite cheap). Just another thing to factor into response.user166390– user1663902010-12-02 06:36:42 +00:00Commented Dec 2, 2010 at 6:36
Add a comment
|
7 Answers
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.
5 Comments
Jahan Zinedine
but actually in recent languages it's a preferred approach as far as I know, like what we see in Functional Programming languages. It's a simpler problem solving technique and after a minor try for a ordinary programmer it will catch the idea and can use it effectively
lijie
@Jani: functional languages still tend to provide a
+ function (time complexity is different).
Tony Delroy
@Jani: functional programming languages have been around for a long, long time, and there's no significant momentum for change in the programming community's preference for or use of them or recursion. Both have their place, which is real and naturally enough roughly reflected in their current proportion of usage. Most "ordinary" professional programmers do understand recursion, and already use it when it makes solving a problem simpler.
Jahan Zinedine
@Tony Yes functional languages have existed since the long time ago, but community recently give it the worthy attention it takes, must say languages that make boom recently, and in the case of recursion concept, IMHO in every introduction to programming book you can find the definition and use of recursion. although at the first look it's confusing but later on it will be seen as an intuitive way for problem solving.
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")
EDIT
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.
8 Comments
paxdiablo
Err, gcc does tail-end just fine and you cannot make a blanket statement like C++ doesn't detect stack overflow. The ISO standard says nothing about that and, in fact, I've worked with compilers that do detect stack overflow.
lijie
it says nothing, therefore a compiler is free to ignore stack overflow. i tend to work with compilers that don't (embedded programming, without MMUs :( ).
Matthieu M.
@lijie: too bad your compilers are simple. gcc and Clang, at the very least, implement tail call optimization (in fact Clang also implement near-tail call optimization, I don't know about gcc but I guess they do too).
J-16 SDiZ
gcc does tail call opimization. in fact, it would change some non-tail calls to tail-call. see ridiculousfish.com/blog/archives/2010/07/23/will-it-optimize
Konrad Rudolph
@lijie: I understand the sentiment. On the other hand, (particularly with C++), programmers often need to expect that the compiler knows what it’s doing. For performance-critical code, this is a hard requirement. In a way, modern C++ style relies on smart compilers. Most good C++ is completely broken, performance-wise, when compiled with a legacy compiler. Tail-call support is actually pretty basic in that regard. I’m currently working for a library relies on much more sophisticated optimizations (and it’s the expressed goal of this library to be the fastest possible).
|
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.
Comments
Recursion is often avoided because of the stack overflow issue. Iterative solutions don't have that problem and all recursive problems can be rewritten to use iteration (some more easily than others). In addition, many programmers simply aren't that familiar with recursion (it doesn't turn up that often)--someone maintaining code later on may not understand what's going on and make a modification which screws something up. That's generally a bad thing. Recursion in other languages, particularly functional ones, is often seen more frequently, due to how they handle it.
Comments
Recursive functions are usually avoided because
- It may take too much of gray cells
- It may take too much of stack space than what is desirable/permissible.
They also may have undesirable consequences if the function is not reentrant.
3 Comments
Chubsdad
@paxdiablo: the reentry to the function may be affected if the recursive function is synchronized on a mutex or critical section at entry e.g.. Probably multithreaded is not the right word there. what do you say?
paxdiablo
You gave an answer to your own question @Chubsdad, the term is "reentrant" :-)
Chubsdad
@paxdiablo: Thanks. Edited. As I mentioned, it requires far more gray matter than I have :)
Unless the compiler can optimize recursive calls out (tail-recursion optimization) each invokation needs a copy of all parameters and local variables plus the return address. That stuff has to be stored somewhere which is usually on the stack. So impact is amount of memory for one invokation multiplied by the number of subsequent invokations.
Also when invokation goes deep down into recursion newer egions of stack are occupied and this can causes cache misses which can slow down execution and can also be attributed as memory impact.
Comments
Think about how the recursion actually works, and the impact on memory is clear. Start by understanding how function calling in general works. You might want to start here.
