A problem can be solved and get the same result as a loop or through Recursive calls to a function.
A problem can be solved and get the same result as a loop or through Recursive calls to a function.
The answer depends heavily on context.
There are several situations where using recursion is more efficient.
One of these is when you know in advance that there will not be many call levels and the iterative version would spend more processing and memory with a stack of states.
Another is when there is the possibility of Tail Call Optimization ), as already discussed here in SOPT at some questions .
Every recursive implementation can be "converted" into iterative in some way. In the latter case, a stack is used to simulate the state of each call. See some links SO in English for a more complete discussion.
The problem is that sometimes the solution is so more complex that in practice the recursive version has a better cost-benefit. An example that I know personally is the case that can be seen in my question and answer on the iterative (non-recursive) version of the LCA algorithm .
Recursive algorithms can naturally take advantage of caching and memoization techniques to get much faster results.
Recursion as a general rule should be avoided mainly for the following reasons:
There is no absolute answer, as there are cases where the iterative solution is difficult to obtain or performs less than recursive. However, whenever possible, you should opt for a non-recursive solution.
I agree with utluiz's answer , I would just like to add the following:
Considering that a programming language being used has both features ...
Having both features is not enough, it is also important to know if they are implemented efficiently and if they are used extensively in programs written in that language.
As for efficiency, half of the answer has already been given: language needs to support Tail Call Optimization for recursion to be feasible in most cases. Unless for a particular problem the iterative solution also employs a stack, and that stack is as or more inefficient in memory consumption than the calling stack, the [naive] recursive functions will in general less efficient than iterative.
The other half refers to languages that support iterative constructs, but the modus operandi of them is recursive in nature. In this case, the iterative version of the program may be less efficient than the recursive version! Example (Prolog; comments in JavaScript):
soma(Inicio, Fim, Return) :- % function soma(Inicio, Fim) {
dynamic(x/1), % var x;
assertz(x(0)), % x = 0;
between(Inicio, Fim, N), % for ( var N = Inicio ; N <= Fim ; N++ ) {
retract(x(X)), % var X = x; x = undefined;
X1 is X + N, % var X1 = X + N;
assertz(x(X1)), % var x = X1;
fail; % }
x(Return), % return x;
abolish(x/1). % } // acabou o escopo de x
?- soma(1, 10, Resultado).
Resultado = 55.
Taking the fact that the syntax is ugly and verbose (which could easily be fixed with a syntactic sugar >), the problem with this code is that the use of assert
and retract
is relatively expensive in Prolog, so a recursive solution [with recursion of the tail] would be much more efficient:
soma(Inicio, Fim, Return) :- soma(Inicio, Fim, Fim, Return). /* Resultado Parcial = Fim */
soma(Inicio, Inicio, RParcial, RParcial). /* Se o início for igual ao fim, retorne o Res. Parcial */
soma(Inicio, Fim, RParcial, Return) :-
RParcial1 is RParcial + Inicio,
Proximo is Inicio + 1,
soma(Proximo, Fim, RParcial1, Return).
As for being used extensively, there comes the issue of code uniformity and maintainability. If the vast majority of programs in language X use iteration, using recursion when there is a perfectly simple, concise, and efficient alternative that solves the same problem via iteration, we want to look for a problem:
The same arguments should also apply to the opposite scenario (use iteration in a predominantly recursive language), but I do not have enough experience to express my opinion (in the case of Prolog, there are many situations in which the iteration is the best tool yes, unlike the impression that a beginner in that language might have - there's even a built-in specific to this ... ).
Whenever possible avoid this feature . Recursive calls are interesting and elegant, but they spend more memory (because they have to store the N recursive calls and return them respectively) and on more limited platforms like PIC, you can pop the PC limit if you do not take care (120 calls) in the PIC18 family.
On the other hand there are problems in which the use of recursion is common because to solve the problem without recursion it would be necessary to create a stack to keep the order of the calls as in torre de hanoi
or mergesort
.
Edited:
The answer was wrong because every recursive problem can be written in loop form (reference) .
Reading tip: How to remove recursion using stack - ( English)