Recursive function vs loop

Question

when would we use a recursive function instead of a loop? is a recursive function like a loop?

Answer 1

Generally I would not advise you to use recursion, because the execution speed of a recursive algorithm is O(2^n )(computer does the same work over and over). Loops are generally faster O(n) (linear time), even 2 nested loops have better performance O(n^2). In case you don't know what it means google Big O notation.

Answer 2

Yes, a recursive function is in fact like a loop, where the body of "the loop" is in fact the function body. Likewise a recursive function needs to do some conditional test (exactly like a loop) to know when it is time to exit the "loop".

For example this:
void foo() {
for(int x = 0; x < 10; x++)
cout << x << endl;
}
... will print x and increment x ten times.

But so will this:
void bar(int x) {
if(x < 10) {
cout << x++ << endl;
bar(x)
}
}
void foo() {
bar(0);
}

Note that even though the 2 versions have equivalent results, there is a big difference between them: the 2nd version causes an additional 10 instances of the bar function and its argument x to be pushed onto the stack during the execution of foo, whilst the 1st version of foo executes the loop entirely in the context of the foo stackframe.

So the 1st version is much more efficient.

Recursion is very useful in some contexts to give very readable and minimal solutions, but often at the expense of performance.

Andrei Alexandrescu (C++/D guru) once gave a talk where he used this very succinct recursive factorial function (which is the poster child for recursion) as an example (the talk was about purity, but it does not really matter for our discussion):

ulong factorial(uint n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}

Very nice and short! But the conclusion was that this simple loop version is a better solution:
ulong factorial(uint n) {
ulong result = 1;
for (; n > 1; --n) {
result *= n;
}
return result;
}

In case you wonder: the above factorial functions are actually D code, but besides the slight differences in type declarations (which you will be able to easily read), they are identical to the C++ versions in syntax and consequences. In fact, I've ignored Andrei's discussion on the impact of purity as that is outside the scope of your question.