3

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.

2 Answers 2

3

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
6
  • When you are saying: "while the first, on account of the + will require an additional stack frame" there will only be one additional stack frame at any time? C adds a new stack frame for each function call I believe, so does this mean recursion in Scheme is more efficient in this way? If I'm missing something please let me know; this is merely a curious thought and I can't take any courses that go in-depth on this until next year. Thanks for the awesome answer by the way. Jan 24, 2014 at 0:43
  • Tail call optimization is compiler magic. The Scheme standard requires that compilers implement it. Tail call optimization in implemented using jump instructions instead of call. Tail call optimized recursion is more efficient as a consequence.
    – Bhaskar
    Jan 24, 2014 at 0:52
  • Ah, so if there is no tail recursion (such as in the first function) then the efficiency of recursion in Scheme is the same in C? Jan 24, 2014 at 0:57
  • There are more details to it, Scheme is interpreted and C is compiled. Assuming all things being equal, jump instructions will be faster than function call, or recursion without tail TCO will be worse. GCC being compiled probably implements non TCO recursion that is faster than Scheme interpreters.
    – Bhaskar
    Jan 24, 2014 at 1:14
  • 1
    @Bhaskar Scheme doesn't require interpretation and there are several compilers in existence.
    – molbdnilo
    Jan 24, 2014 at 14:34
2

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.

1
  • I had no idea Racket can't have stack overflows... thanks! I will read up on some of the papers you have provided this weekend. Jan 24, 2014 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.