CODEWITHSUNDEEP
recursiondata-structuresstack
marshblocker
marshblocker

Reputation: 83

Maximum depth of a theoretical function stack due to a recursive function?

If we have a theoretical stack memory that never gets full and we have a simple recursive function

recurse(n):
    if n > 0:
        recurse(n-1)
        recurse(n-2)
    return

Is it reasonable to argue that the theoretical stack has at most n stack frames at any point in the execution of recurse(n) since it is impossible for recurse(k) to be on top of recurse(i) if 0 <= k < i <= n, since this implies that recurse(i) called recurse(k) (which is impossible based on the function body). If my reasoning is correct, then the maximum depth must be the case when the function stack looks like the following:

(BOTTOM-MOST)|recursion(n)|recursion(n-1)|...|recursion(2)|recursion(1) (TOP-MOST)

Upvotes: 1

Views: 268

Answers (2)

Mulan
Mulan

Reputation: 135377

It's easy to prove. Map it out for yourself -

recurse(0)

recurse(1)
  recurse(0)
  recurse(-1)

recurse(2)
  recurse(1)
    recurse(0)
    recurse(-1)
  recurse(0)

recurse(3)
  recurse(2)
    recurse(1)
      recurse(0)
      recurse(-1)
    recurse(0)
  recurse(1)
    recurse(0)
    recurse(-1)

recurse(4)
  recurse(3)
    recurse(2)
      recurse(1)
        recurse(0)
        recurse(-1)
      recurse(0)
    recurse(1)
      recurse(0)
      recurse(-1)
  recurse(2)
    recurse(1)
      recurse(0)
      recurse(-1)
    recurse(0)

This is why fib(n) for large n will not overflow the stack, and instead tie up your CPU for a long time. For small n such as n = 20, the result is computed in 1,048,576 steps, but only uses 20 frames -

function fib(x)
{ if (x < 2n)
    return x
  else
    return fib(x - 1n) + fib(x - 2n)
}

console.log("result %s", fib(20n))
// result 6765

For larger n like n = 200, it would take a staggering 1,606,938,044,258,990,275,541,962,092,341,162,602,522,202,993,782,792,835,301,376 computations, but with only a stack depth of 200, would not cause an overflow. However even at 1,000,000,000 computations per second, it would take 50,955,671,114,250,072,156,962,268,275,658,377,807,020,642 years to complete -

function fib(x)
{ if (x < 2n)
    return x
  else
    return fib(x - 1n) + fib(x - 2n)
}

console.log("result %s", fib(200n))
// result ...

If you tried to run fib(200) above, JavaScript will cause you browser to hang until long after the sun dies. Refresh this tab and we can compute the answer in just 1 millisecond. This rewrite of fib uses linear recursion, computing n = 200 will only take 200 steps and 200 frames -

function fib(x, a = 0n, b = 1n)
{ if (x == 0n)
    return a
  else
    return fib(x - 1n, b, a + b)
}

console.time("fib(200)")
console.log("result %s", fib(200n))
console.timeEnd("fib(200)")
// result 280571172992510140037611932413038677189525
// fib(200): 1.000ms

If you use a while loop, it can be done in 200 steps and just 1 frame. But that's not recursion, so maybe it's not worth talking about in this post.

Upvotes: 0

kaya3
kaya3

Reputation: 51102

When n = 0 there is one stack frame for the function call itself - you can't have less than one stack frame for any n - so the formula for the maximum number of stack frames is max(1, n+1), not n exactly. Otherwise your reasoning is correct, and this formula can be proved by induction:

  • In the base case when n <= 0, there is one stack frame, which is equal to max(1, n+1) because n+1 <= 1.
  • Otherwise when n >= 1, two recursive calls are made, one with a stack depth of max(1, n) and the other with a stack depth of max(1, n-1) by the inductive hypothesis. So the maximum stack depth including the current stack frame for the call on n equals 1 + max(max(1, n), max(1, n-1)). This can be simplified to 1+n because n is the largest of the max operands, and 1+n does equal max(1, n+1) as required.

Upvotes: 1

Related Questions