Editing Stack overflow (section)

===Very deep recursion===
A recursive function that terminates in theory but causes a call stack buffer overflow in practice can be fixed by transforming the recursion into a loop and storing the function arguments in an explicit stack (rather than the implicit use of the call stack). This is always possible because the class of [[primitive recursive function]]s is equivalent to the class of LOOP computable functions. Consider this example in [[C++]]-like pseudocode:

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
void function (argument) 
{
  if (condition)
    function (argument.next);

}
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
stack.push(argument);
while (!stack.empty())
{
  argument = stack.pop();
  if (condition)
    stack.push(argument.next);
}
</syntaxhighlight>
|}

A primitive recursive function like the one on the left side can always be transformed into a loop like on the right side.

A function like the example above on the left would not be a problem in an environment supporting [[tail-call optimization]]; however, it is still possible to create a recursive function that may result in a stack overflow in these languages. Consider the example below of two simple integer exponentiation functions.

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
int pow(int base, int exp) {
    if (exp > 0)
        return base * pow(base, exp - 1);
    else
        return 1;
}
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
int pow(int base, int exp) {
    return pow_accum(base, exp, 1);
}

int pow_accum(int base, int exp, int accum) {
    if (exp > 0)
        return pow_accum(base, exp - 1, accum * base);
    else
        return accum;
}
</syntaxhighlight>
|}

Both <code>pow(base, exp)</code> functions above compute an equivalent result, however, the one on the left is prone to causing a stack overflow because tail-call optimization is not possible for this function. During execution, the stack for these functions will look like this:

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625
</syntaxhighlight>
|}

Notice that the function on the left must store in its stack <code>exp</code> number of integers, which will be multiplied when the recursion terminates and the function returns 1. In contrast, the function at the right must only store 3 integers at any time, and computes an intermediary result which is passed to its following invocation. As no other information outside of the current function invocation must be stored, a tail-recursion optimizer can "drop" the prior stack frames, eliminating the possibility of a stack overflow.