fn sum(n):
if n == 0:
return 0
else:
return n + sum(n - 1) // A
When n = 1000, your function call stack will have to hold ~1000 calls (fn(1000), fn(999), fn(998), fn(997), and so on...), before it's able to compute the sum. This is because the return statement in line A above, needs to keep track of the variable `n` from the calling function in order to be able to compute the return value. If only there was some way to eliminate that variable `n`... fn sum_tail(n, pre_sum):
if n == 0:
return pre_sum
return sum_tail(n - 1, pre_sum + n) // B
fn sum(n):
return sum_tail(n, 0)
In this solution, the return statement at line B does not depend on any variable from the calling function (it simply passes that value on to next function call), and so the calling function can immediately be popped off the stack, saving stack space and making your solution more memory-efficient.