Question

I am a university student studying Racket/Scheme and C as introductory courses for my CS degree.

I have read online that it is generally best practice to use iteration as opposed to recursion in C because recursion is expensive due to saving stack frames onto the callstack etc...

Now in a functional language like Scheme, recursion is used all the time. I know that tail recursion is a huge benefit in Scheme and it is to my understanding that it only requires one stack frame (can anybody clarify this?) no matter how deep the recursion goes.

My question is: what about non-tail recursion? Does each function application get saved on the callstack? If I could get a brief overview of how this works or point me to a resource I would be grateful; I can't seem to find one anywhere that explicitly states this.

Was it helpful?

Solution

Tail call elimination is required by Scheme. Code that isn't tail call recursion will require an additional stack frame.

For a moment let us assume that javascript supports tail call optimization, the second of these function definition will use only 1 stack frame, while the first, on account of the + will require an additional stack frame.

function sum(n) {
   if (n === 0)
      return n;
   return n + sum(n - 1);
}

function sum(n) {
  function doSum(total, n) {
    if (n === 0)
       return total;
    return doSum(total + n, n - 1);
  }
  return doSum(0, n);
}

Many recursive functions can be written for tail call optimization by putting the result of the computation on the stack

Conceptually invocations for the first definition look like this

3 + sum(2)
3 + sum(2) = 3 + 2 + sum(1)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 6
3 + sum(2) = 3 + 2 + sum(1) = 6
3 + sum(2) = 6
6

invocations for the second definition look like this

sum(3, sum(2)) = sum(5, sum(1)) = sum(6, sum(0)) = 6

OTHER TIPS

Yes, a call in a non-tail position needs to add something to the stack so it knows how to resume work when the call returns. (For a more thorough explanation of stacks, tail calls, and non-tail calls, see Steele's paper Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO linked from the lambda papers page at readscheme.org.)

But Racket (and many other Schemes, and some other languages) implement "the stack" so that even if you have deep recursion, you won't run out of stack space. In other words, Racket has no stack overflows. One reason for this is that the techniques for supporting deep recursion coincide with the techniques for supporting first class continuations, which the Scheme standard also requires. You can read about them in Implementation Strategies for First-Class Continuations by Clinger et al.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top