Is it always possible to rewrite a program written using recursion, to one that does not use recursion in C++ and what is the performance view point?

Question

Just wanted some gyan on this question, at performance point of view and also please explain with respect to about how/Why Stack and Ackermann Function might be involved in this, is it okay to use it every time in C++ ? because it appears for me that each recursive program does indeed have a non-recursive implementation.

Answer 1

You can implement nearly every recursive programm non-recursivly but there are certain programms where using recursion might result in better perfomance over all. If you really want to make sure that you're solution is the fastest I would use the chrono library and create 2 timestamps to measure how long the recursive vs. the non recursive functions needs.

Answer 2

Most of the problems which involve looping can be solved using recursion. So they are grouped into a special type namely Primitive Recursion. Then there are problems not belonging to this category. One such example is the famous Ackermann function. There are some problems where recursion maybe a better approach, for example the Tower of Hanoi problem. It will be much much difficult to solve it without recursion. Again, sometimes you are better off using loops as recursion will call a stack for every process and many a times there will be repeated calculation for the same thing and sometimes there can be stack overflow for the size of the stack can be exceeded. An example is when you are trying to implement the Fibonacci series with recursion.So it depends on the problem which approach you are going to take. Recursion can be optimized by supplementing it with memoization where you are going to save a calculation in a memo(hence the name memoization) so that there is no need to calculate it thereafter.

Answer 3

Abundance of resources is available on the internet on recursion vs iteration discussions, e.g. here and here.

For languages like C/C++, I would go for recursion only if some (rather most) of the following conditions are met:

• The results are needed only after completion of whole process

• Repetitive dynamic memory allocations or resizing for every iteration are quite demanding

• Algorithm complexity causes problems in iterative implementation

Performance: Iteration may be performant in most cases yet you must time both implementations to make your decision.

Hope this helps making your decision