2

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.

mr_T
  • 2,571
  • 3
  • 22
  • 39
  • 7
    Recursion is used in C++ like in any other programming languages or in any other place or city... – nbro Nov 26 '14 at 09:39
  • 2
    If you are expecting tail call optimization, one sneaky pitfall is destructors. If there are any destructors that need to run as part of leaving the function, they will have to run after any called functions return; this destroys the possibility for tail call optimization. You can limit the lifetime of your objects by introducing additional explicit scopes that end before the `return`-statement. – Magnus Hoff Nov 26 '14 at 09:53
  • 2
    @nbro: No, some programming languages _guarantee_ tail call optimization. That makes a huge difference. – MSalters Nov 26 '14 at 10:09

3 Answers3

5

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

justin
  • 104,054
  • 14
  • 179
  • 226
  • 2
    Rule of thumb: `O(log N)` recursion depth is OK, `O(N)` is not OK, `O(sqrt(N))` is probably not OK. – MSalters Nov 26 '14 at 10:11
  • 2
    @MSalters Either that, or `N` is a known small number, probably constant. I'm thinking of backtracking algorithms, like the 8 queens problem, or solving Sudoku. Recursion depth is clearly `O(N)`, but `N` is a known relatively small constant (8 for the 8 queens problem, 81 for Sudoku). And trying to solve backtracking without recursion is something I'd rather not attempt. – James Kanze Nov 26 '14 at 10:18
  • @JamesKanze: There's always the problem of defining `N`. For instance, in the 8 queens problem, there are 8 possible positions in each of the 8 rows, so you have 8^8 possible positions to consider. Your backtracking algorithm is fundamentally the O(log(8^8)) solution to that. – MSalters Nov 26 '14 at 10:43
  • @MSalters For the 8 queens problem: there are only 8 columns, with at most one queen in each column, so your backtracking is: choose a position for the queen in the current column, then recurse into the next. So `N` here is the number of columns. – James Kanze Nov 26 '14 at 10:46
  • @JamesKanze: I know the puzzle as just "put 8 queens on a chess board so they don't attack each other", which is technically a search space of `64! / (56! * 8!)` positions. The definition of `N` depends a bit from the direction by which you came to a solution. – MSalters Nov 26 '14 at 10:53
  • @MSalters The problem is "put 8 queens on a chess board so they don't attact each other". But the search space is limited by the fact that you know up front that you can have at most one queen per column (and in order to have 8 queens on an 8x8 board, you need exactly one queen per column). The problem then becomes one of choosing which row in each column on which to place the queen. – James Kanze Nov 26 '14 at 11:46
  • @MSalters With regards to the search space: the search space and the depth of recursion aren't equal. I tend to think of such things in terms of a decision tree: even with my approach to the 8 queens problem, you have an 8 way decision tree, to a depth of 8 (which means 8^8 leaves). But it's the depth alone which limits recursion. – James Kanze Nov 26 '14 at 11:50
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.

Community
  • 1
  • 1
Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
0

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.

Resource
  • 524
  • 4
  • 16