4

I dont understand why this is forward recursion:

int count(int x) {
    if(x<=0) return 0;
    return 1 + count(x - 1);
}

It's a question on a practice exam, and the answer is that its forward recursion. Why is this the case? How could I distinguish between the two?

Derek 朕會功夫
  • 92,235
  • 44
  • 185
  • 247
Snowman
  • 31,411
  • 46
  • 180
  • 303
  • practice question part 2 - how do you make it tail recursive? – jon_darkstar Nov 15 '10 at 21:04
  • possible duplicate of [tail recursion vs. forward recursion](http://stackoverflow.com/questions/3042954/tail-recursion-vs-forward-recursion) –  Nov 15 '10 at 21:19

2 Answers2

8

You're doing an addition after calling yourself. Tail recursion means absolutely nothing can be after

If you understand the implementation, it's clear why.

Say we call count for the first time from main, which is at program counter 0xAAA. It then does most of its method. We'll say the recursive call to count is at 0xBBB for this stack frame. If you're using tail recursion, when calling itself, it can set the return address as 0xAAA (just go straight to the code that called me). If it's doing anything after, it must set the return address as 0xBBC (the address of the addition). Because it doesn't need stack frames to store return addresses, it's also much easier to transform the recursion to iteration. When count calls itself, it can just jump to the beginning of the method.

The solution (to the trivial example) is to build up the result in another parameter:

int count(int x, int res) {
  if(x<=0) return res;
  return count(x - 1, res + 1);
}

Note we do nothing after.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
  • 1
    It's indeed not very clear as it's both in the return statement. But the very last call is `1 + result_of_recursion`, and not the recursion itself. – extraneon Nov 15 '10 at 21:03
  • 1
    In addition to where the method returns to, it can also optimize away adding stack frames, correct? – Mark Peters Nov 15 '10 at 21:14
  • @Mark, true, I'll add a note about that. – Matthew Flaschen Nov 15 '10 at 21:16
  • Thats weird I thought I added a comment here..anyway I said that I had no idea what you did in your example. Why use addresses and program counters and complicate this even more? Anyway you can do a comparison of tail recursion and forward recursion or come up with a clearer (more beginner-ish) explanation? – Snowman Nov 15 '10 at 23:51
  • @fprime, the beginner explanation is just that you're doing something (addition) after the recursive call, so it can't be tail recursion. – Matthew Flaschen Nov 16 '10 at 02:59
  • @Mathew Even though function doesn't traverses back the stacks, but it expands creating new stack for every recursive call, thus consuming a lot of space. Iteration saves us from creating new stack frame for each call. Does tail recursion only saves us in memory returns from one stack to other? If so, shouldn't we try to use iteration at the places where we can? – Sanjeev Kumar Dangi Mar 13 '11 at 18:45
  • @Sanjeev, I don't really understand your question, and it seems like it should be asked separately. There is only one call stack (not stacks). – Matthew Flaschen Mar 14 '11 at 01:45
4

Did you look at this SO question, tail vs forward recursion?

Matthew has the answer,and the long form would be that:

int count(int x) {
  if(x<=0) return 0;
  return 1 + count(x - 1);
}

can be written as (and is expanded as something like):

int count(int x) {
    if(x<=0) return 0;
    int tmp_result = count(x - 1);
    return 1 + tmp_result; // e.g. recursion is not last
}
Community
  • 1
  • 1
extraneon
  • 23,575
  • 2
  • 47
  • 51