Recursion vs. Iteration in C/C++?

Question

In my computer science classes I was always told that any recursive solution could be rewritten using iteration. But nobody ever said that the reverse was true, that any iterative solution could be rewritten using recursion. Is that the case or not?

Answer 1

That is so. Functional programming, for example, has recursion as its only control structure.



The loop:



boolean condition = init();

while (condition)

{

... condition = statement();

}



...is a very generic version of a while loop. I've made the loop initialization and body into functions and distilled the loop continuation condition down to a single boolean variable. A recursive version is:



bool loop_as_recursion(bool condition)

{

... if (condition)

... {

... ... condition = loop_as_recursion(statement());

... }

... return condition;

}



then call with:



loop_as_condition( init() );



A for-loop replacement will carry the current "loop index" as a parameter, updated upon the recursive call to have a new value in the next "iteration". Try working that out as an exercise in "thinking functionally".



I don't claim that this is the nicest way to solve a problem. I'm just pointing out that it is possible. Recursion is a nice way to describe certain problems, but I don't think it's the only tool I want in my kit.

Answer 2

Recursion Vs Iteration

Answer 3

Theoretically speaking, that is correct.



However, in practice, most programming frameworks add extra function data to the stack on every recursive call, and there's a limited amount of stack space. As a result, the 'naive' approach to using recursion for iteration can easily exhaust the stack space and crash the program where a standard iterative solution would work fine. There may or may not be a simple technique for getting around this in any particular case. At any rate, iteration is usually faster than recursion.

Answer 4

It is very well correct.

It is the established fact.

Not all problems will be having recursive relation ships thus we can not have a recursive solution for any iterative solution.

Answer 5

I think that it's false.



For example, a method that I've used to get solutions is known as the bisection method. It works well for monotonic functions where you're solving



find x0 such that f(x0) = y0

where f(x) is a monotonic function and you're given y0.



Bisection is a very easy iterative solution but I see no way of doing it recursively...although as I type this I'm thinking of how I would try it...



Great question. I've starred the question to attract the experts.