-
recoursion or loops?
My Uni-teacher seems to love recoursive functions, and so I get strange counting-exercises frequently. I've heard where ever I can solve an exercise with a recoursive function I could also use loops. Loops are said to be executed more quickly than recoursive functions, and they also need less storage. Is there any good reason to prefer recoursive functions? (My teacher says they're easier to understand. - ???)
-
A loop is often faster than recursion. Each time a recursive function calls itself, it needs to set up stack, branch then unwind the stack again. A loop does not have that overhead, (and incidentally, does not run the risk of overflowing the stack).
>>> My teacher says they're easier to understand.
I've encountered that argument before, and would simply disagree. "Easy to understand" is not an objective statement. Whilst some people may find it easier, others find it more difficult. Using recursion for the sake of it is bad practice, use what is less likely to cause confusion.
Another factor is that some operating systems require you to specify in advance your stack size. This can be difficult if you are using recursive functions and you can't specify in advance how deep the recursion will be - you tend to end up requesting excessively large stacks to cover the worst case scenario, that can frequently lead to wasted resources.
-
Alot of c compilers can optimize a function that is written this way
Code:
void print_hello(int n)
{
if (n != 0) {
printf("Hello\n");
print_hello(n - 1);
}
}
The output from gcc with optimization is
Code:
print_hello:
pushl %ebp
movl %esp, %ebp
pushl %ebx
pushl %eax
movl 8(%ebp), %ebx
.L19:
testl %ebx, %ebx
je .L18
subl $12, %esp
pushl $.LC0
call printf
decl %ebx
addl $16, %esp
jmp .L19
.p2align 2
.L18:
movl -4(%ebp), %ebx
leave
ret
So a iterative solution written recursively doesn't always eat up stack space.