MHB Just a question about recursive functions, no code.

[carl123]

What are different ways of ensuring efficiency in a recursive function in C++? i.e. Prevent calling your recursive function when not necessary.

 

[Evgeny.Makarov]

Prevent calling your recursive function when not necessary.

Ha-ha. If you do any computation that is unnecessary, then you are a... strange programmer.

Some C++ compilers do tail call optimization. Then if the recursive call is the last thing a recursive function does, no memory is allocated on the stack, unlike in a normal function call, and the recursion behaves as a loop. This is important because otherwise a recursive function can easily run out of stack space.

Sometimes it makes sense to store values already computed by a recursive function to avoid re-computing them. Fibonacci numbers is one example. Memoization and dynamic programming are two techniques that store intermediate results.