What are the main guidelines for using recursion in C++?

Question

Being relatively new to C++ I wonder whether there are specific things to take into account when using recursion because of the specifitivity and low-levelness of the language in comparison with languages such as Python, Java and/or functional languages.

Also, I wonder whether there are many differences between various compilers with respect to how they treat recursion (especially concerning tail recursion). I currently work with gcc on CodeBlocks and VS2010.

Answer 1

Recursion in C++ should be bound, and not descend very deep -- especially when your implementation is capable of creating nontrivial stack allocations. If your program does not meet those requirements, then you should employ another approach (e.g. iterative).

Each function call requires some stack storage, and your function parameters also require stack storage. How much stack storage you get depends on your implementation/environment. Modern desktop systems will generally not give you more than a few MB. Other implementations will provide you with much less.

If your call exceeds the boundary of the thread's stack, then you will get a stack overflow.

There are some optimizations which can eliminate nesting calls in recursive functions, but your implementation should not depend on this behavior because it is unsafe (e.g. that optimization may no longer be performed after you update the compiler, change your build settings, or as your codebase evolves).

Answer 2

I would pay attention to any pointers, pointers-to-pointers etc used in your recursive function, in case you find yourself standing on your own tail.

Answer 3

You should be aware that most compilers / execution environments decide on some particular stack size - 1MB through 8MB is pretty typical - and C++ runtimes aren't - in my experience - ever designed to increase that dynamically. Some systems may provide even less stack for threads started by the program code than they do for the main thread started by the OS. On Linux - for example - your shell may let you use ulimit to set a stack size before running an application, but some systems require privileges to grow the size or may have kernel limits.

Many C++ compilers do pretty well at providing tail recursive function optimisations so memory usage doesn't grow with depth of recursion, but when that fails you may hit the stack size limits mentioned above.

This is pretty typical for most languages I've used (python, ruby, C, pascal etc.) and C++ objects tend to be pretty minimal and memory efficient so you'd likely do a little better than with equivalent data and stack size in say python.

Still, you mention "functional languages" which is so open-ended and some are so "experimental" I'd bet some actually allocate "heap" memory dynamically for recursion and can grow way beyond what C++ implementations tend to support. Some languages that run/interpret byte code on virtual machines might do that too.