Should one avoid using recursive call in C/C++?

Should one avoid using recursive call of functions in C/C++?

I work on machine learning/data mining, so it is very critical for me to make my code scalable.

When I was using Java, I avoided using recursive call as much as possible because I often got my call stack overflowed. Although there are options to control the amount of memory assigned to the call stack, I thought having my program dependent on smaller number of parameters is more desirable. Therefore when it is clear how to implement without recursive call, possibly using a stack managed by myself, I did so. But I am not sure this is a right discipline even in Java.

In my knowledge, there is no call stack in C/C++, so I would not worry about overflowing it. Thus, I am curious: would 开发者_开发技巧one try to avoid using recursion, or is it encouraged, or it is problem specific, in terms of scalability of your program?

---

There is no single correct answer to this question. For some problems, recursion works very well. For other, it doesn't.

In my knowledge, there is no call stack in C/C++

Just to be clear, this is incorrect: there is a call stack in all implementations of C and C++ that I know of.

---

In my knowledge, there is no call stack in C/C++, so I would not worry about overflowing it

Huh? Of course the standard doesn't talk about call stack, but indeed there is one on most, if not all, implementations.

Now, should recursion be avoided? First of all, it is well-known that every recursive function can be rewritten iteratively (i.e. without recursion). And also, sometimes iterative solutions are faster than recursive ones. But for some tasks, for example DFS in a graph, recursion is so simple and useful that you shouldn't avoid using it unless you have a good reason not to. An iterative solution for the same DFS is almost as simple, but requires more typing...

My 2 c.

---

The call stack in C & C++ is kind of like the vtable in C++ in one respect - it's not mentioned in the standard as far as I know, i.e., that implementation is not mandated, but for all practical purposes, it's almost always implemented that way.

Granted there are some esoteric architectures, especially in the embedded world, that might eschew the stack. The PIC is an example of a stack-unfriendly architecture, and some tiny microcontrollers don't support a stack, and least not directly. And in certain situations use of the stack can be eliminated anyway (inline functions or aggressive optimization for function calls, use of registers for local variables instead of stack space).

Anyway, to your question... this is a very subjective question that usually boils down to one question: can you afford it?

If you have enough stack space and the recursion won't be deep enough to blow your stack, recursion is often the right choice. Not always, but often.

But you have to understand your architecture, your platform, your toolset, etc. and know how large your stack is. With many multi-tasking embedded systems, for example, your stack size is determined at the time the thread/task is created, and it won't "grow as needed". Other simple (embedded) systems only use a single stack, or maybe one "background" stack and one interrupt stack. Still others allow the stack to grow as needed, within limits, depending on the processor & operating system.

If you're coming from a Java background, I'm not surprised if this kind of discussion is new to you.

---

I often got my call stack overflowed

Then it's YOUR FAULT.

Recursion is a very useful construct when used correctly. Particularly where you need to work with a variable sized set of data structures. Limiting the recursion is trivial:

int recurse(int maxlimit, ...)
{
   if (!--maxlimit) return false; // and throw an exception or something
   ...
   return completed ? finalvalue : recurse(maxlimit, ...);
}

---

Recursion can be a very elegant way to express algorithms. The primary downside in C/C++ is the potential for stack overflow.

Here's a rule of thumb for C/C++:

If the recursion isn't a tail call, then the depth needs to be sub-linear in the size of your data.

For example, if you are recursing to do a DFS of a binary tree, that tree must be balanced such that the recursion depth is O(log n). This ensures there isn't a stack overflow. Don't use non-tail recursion to traverse a linked list (O(n) depth).