6

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?

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
d_ijk_stra
  • 190
  • 1
  • 6
  • 19
    There *is* a call stack in C/C++. – lhf Aug 03 '11 at 16:16
  • The stack can certainly also overflow in C/C++. Very briefly I'd use an explicit stack (rather than relying on recursion) when the maximum recursion depth scales at a greater rate than O(lg N) in the data size. I.e. I'd have no problem using recursion in a balanced search tree, but would be wary when manipulating a linked list. – user786653 Aug 03 '11 at 16:18
  • 8
    to quote an anonymous SO user: "What is this C/C++ language you speak of? I only know C and C++..." – Necrolis Aug 03 '11 at 16:24
  • 1
    Tail self-recursion or `isEven`/`isOdd` recursion is well amenable to optimizations which eliminate a growing stack altogether, so if it's appropriate, there's no universal reason to avoid that. – Kerrek SB Aug 03 '11 at 16:25
  • 8
    "In my knowledge..." With such an ambitious nick, you ought to know better, really. – sbi Aug 03 '11 at 16:32
  • Goddamnit. This question has absolutely nothing to do with either C or C++, and it's everything to do with the hardware platform they run on. – Puppy Aug 03 '11 at 16:50
  • @DeadMG why is it precisely and specifically hardware-dependent? I would think that it is compiler-dependent, which would in large part but not in entirety be driven by the hardware. – San Jacinto Aug 03 '11 at 17:05
  • @san: unless there is a standard that states c or c++ can only be for hardware with a stack, the compilers hardware target will determine if it has a stack or not (though I don't know of any stackless machines/targets, maybe some embedded devices?), thats basically one of the points of higher level languages, to abstract away the oddities of the hardware/low level subsystems – Necrolis Aug 03 '11 at 17:40
  • @Necrolis That's pretty much the same thing I said. Your comment seems a little pedantic. Is there something you want to add beyond what I said? – San Jacinto Aug 03 '11 at 19:08
  • @DeadMG Actually, now that I read it again, I think I interpreted your use of "hardware" as "physical device" whereas I now think you meant "hardware" as "platform," which would encompass O.S. settings and hardware capacities and a host of other things and tend to agree with you but still think it's a fair C and C++ question for a newbie to the languages.. But your comment serves to correct their mistake. My apologies. – San Jacinto Aug 03 '11 at 19:09

5 Answers5

13

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.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
8

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.

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
  • 2
    That's right the standard doesn't mention it (except stack unwinding), and there are plenty of embedded processors without stack. – Gene Bushuyev Aug 03 '11 at 16:22
  • 1
    @Gene: even when mentioning stack unwinding, the standard does not imply or require a call stack at all. It just states that the process of cleaning up when exceptions are thrown is called "stack unwinding". – R. Martinho Fernandes Aug 03 '11 at 16:27
  • @Martinho and Gene, knowing that most implementations have a call stack and the fact that the standard is _silent_ on the implementation details regarding this, do you agree that in this case it's is prudent to code with scalability in mind by making an assumption that there will indeed be a call stack, or some compiler-implemented version of a call stack? – San Jacinto Aug 03 '11 at 17:03
  • @San Jacinto -- there is no universal portability, you have to know the limitations of your platform. In embedded world C/C++ compilers specifically designed with the limitations of the hardware in mind. – Gene Bushuyev Aug 04 '11 at 17:04
  • 1
    This isn't good advice. Only DFS a graph recursively if you can bound the recursion depth. If your graph happens to be a linked list, you can run out of stack depth easily. For many large datasets, its a bad idea to do a recursive DFS (in C/C++ at least). – Taylor Feb 01 '16 at 17:10
  • It is not true that every recursive function can be written iteratively. Now, as for functions that are likely to be used (i.e. not a mathematician writing an arcane and contrived function to prove a point), there are much fewer. In the vast majority of functions you're free to write whichever solution is "cleaner" (however you choose to define cleaner), unless performance or stack limitations push you one way or the other. – Ben Aug 19 '20 at 21:01
  • @Ben: Not only can any recursive function be written iteratively, there is a well-defined procedure for converting any recursive code into iterative code. Can you bring a single example of a recursive function that cannot be implemented equivalently iteratively? – Armen Tsirunyan Aug 20 '20 at 12:13
  • @ArmenTsirunyan The earliest example is the Ackerman Function https://en.m.wikipedia.org/wiki/Ackermann_function – Ben Aug 20 '20 at 17:42
  • @ArmenTsirunyan my apologies, I mistook iterative for primitive recursive, you are indeed correct that any recursive function can be written iteratively. – Ben Aug 20 '20 at 18:26
  • @Ben: No worries, of course there are partially recursive functions that are not primitively recursive .And then there are also functions which are not even partially recursive but those aren't computable anyway - either recursively or iteratively (per Turing-Church hypothesis, I think) – Armen Tsirunyan Aug 21 '20 at 18:31
4

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.

Dan
  • 10,303
  • 5
  • 36
  • 53
3

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, ...);
}
symcbean
  • 47,736
  • 6
  • 59
  • 94
  • 3
    Putting a limit on recursion depth isn't much help if you need to actually compute something. The stack is small. Better to go with iteration in that case. – Taylor Feb 01 '16 at 17:06
1

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).

Taylor
  • 5,871
  • 2
  • 30
  • 64