CODEWITHSUNDEEP
recursion
coolcow
coolcow

Reputation: 55

What happens after non-tail recursion bottoms out

I am new to recursion, and have been looking at non-tail recursion. I believe this is where the recursive call is not at the end of the function. I was looking at some recursive code examples, and I am confused about when and how the code after the recursive call is executed. To be more specific, when the current line of the program reaches the recursive call, is that last bit of code executed before actually executing the entire function again, or does the current line of execution immediately jump back to the beginning of the function, only to execute that remaining bit of code after the entire recursion bottoms out? Can anybody please clarify how this works for me?

Upvotes: 1

Views: 67

Answers (1)

Sylwester
Sylwester

Reputation: 48775

Imagine this code here: (I'm using JS here, but it applies to all eager languages)

function add(a, b) {
  return a + b;
}

function sub(a, b) {
  return a - b;
}

function fib(n) {
  if (n < 2) {
    return n;
  } else {
    return add(
      fib(sub(n, 2)),
      fib(sub(n, 1)),
    );
  }
}

console.log(fib(10));

Now when n is 2 or more we we add the result of calling fib on the two predecessors to n. The order between some of the calls are JS engines choice, but sub needs to be called and return before fib can get a value and add needs to be called when both it's arguments have results. This can be rewritten as tail calls using continuation passing style:

function cadd(a, b, k) {
  k(a + b);
}

function csub(a, b, k) {
  k(a - b);
}

function cfib(n, k) {
  if (n < 2) {
    k(n);
  } else {
    csub(n, 2, n2 =>
      cfib(n2, rn2 =>
        csub(n, 1, n1 =>
          cfib(n1, rn1 =>
            cadd(rn2, rn1, k)))));
  }
}

cfib(10, console.log);

Here you see the order which was engines choice is explicit left to right. Each call does one thing then the continuation is called with that result. Notice also that this never returns anything. "return" is only done by continuation, yet it does the exact same thing as the previous code.

In many languages they would compile to the same.

Upvotes: 0

Related Questions