As far as I understand, a tail recursive function calls itself at the very last step (like the return statement) however, the first instance of the function is not terminated until all the other instances are terminated as well, thus we get a stack overflow after a number of instances are reached. Given that the recursion is at the very last step, is there any way to terminate the previous instance during or right before the next instance? If the only purpose of an instance is to call the next one, there is no reason why it should reside in memory, right?
Add a comment
|
2 Answers
Yes, some compilers will optimize tail recursion so that it doesn't require extra stack space. For example, let's look at this example C function:
int braindeadrecursion(int n)
{
if (n == 0)
return 1;
return braindeadrecursion(n - 1);
}
This function is pretty easy; it just returns 1. Without optimizations, clang generated code on my machine that looks like this:
_braindeadrecursion:
00 pushq %rbp
01 movq %rsp,%rbp
04 subq $0x10,%rsp
08 movl %edi,0xf8(%rbp)
0b movl 0xf8(%rbp),%eax
0e cmpl $_braindeadrecursion,%eax
11 jne 0x0000001c
13 movl $0x00000001,0xfc(%rbp)
1a jmp 0x0000002e
1c movl 0xf8(%rbp),%eax
1f subl $0x01,%eax
22 movl %eax,%edi
24 callq _braindeadrecursion
29 movl %eax,%ecx
2b movl %ecx,0xfc(%rbp)
2e movl 0xfc(%rbp),%eax
31 addq $0x10,%rsp
35 popq %rbp
36 ret
As you can see, the recursive call is in there at 0x24. Now, let's try with higher optimization:
_braindeadrecursion:
00 pushq %rbp
01 movq %rsp,%rbp
04 movl $0x00000001,%eax
09 popq %rbp
0a ret
Now, look at that - no more recursion at all! This example is pretty simple, but the optimization can still occur on more complicated tail recursive cases.
Comments
Either: - you can increase the stack size or - do not use recursion, but instead use some sort of looping.
1 Comment
I'm not sure if this answers the question, but while we're at it, there are other options: Switch to an implementation that optimizes tail calls (or just use a language that requires TCO); use trampolining; switch to a dynamically-resized stack on the heap instead of using the hardware stack (maybe that's what you meant with "not use recursion", but I read it as "switch to an equivalent iterative algorithm").