CODEWITHSUNDEEP
c++fibonaccitail-recursion
MrKevKev
MrKevKev

Reputation: 21

Calling itself in Return twice--Tail Recursive or Not?

I understand tail-recursion however I have been assigned to write a code to see what the N'th Fibonacci number is. To begin, this code does work. It's not the best way but it's one way--however I'm starting to worry that it isn't tail recursive. The code is here:

static int fib_tail_helper(int n, int result) {
if (n == 0) {
    return result;
}   
else if (result == 0) {
    return fib_tail_helper(n - 1, result + 1);
}
else {
    return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1, 0));
}
}

int fib_tail(int n) {
/*
// REQUIRES: n >= 0
// EFFECTS: computes the Nth Fibonacci number
//          fib(0) = 0
//          fib(1) = 1
//          fib(n) = fib(n-1) + fib(n-2) for (n>1).
// MUST be tail recursive
*/
return fib_tail_helper(n, 0);
}

I'm mostly worried about the "return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1), 0". I feel as if that would use another stack, and thus be non-tail-recursive... Can anyone give some input?

Thanks!!

Upvotes: 2

Views: 1018

Answers (3)

Louis Newstrom
Louis Newstrom

Reputation: 172

Tail recursion is a clever implementation of recursion, that does not use stack space.

It works like this:
If a function calls itself, as it's last action, then that is called "tail recursion".
In this special case, a compiler can forgo doing an actual function call. It can execute a goto back to the beginning of the function. The code of the function will run again, just as if it had been called. When the function terminates, it will return to the last address on the stack, which is the function that originally called the recursive function.

This approach guarantees that the stack does not overflow, no matter how deep the recursion goes. That is what is so great about tail recursion.

The bad news is that C++ does NOT automatically support tail recursion.

The good news is that it is trivially easy to implement tail recursion.
You simply replace the final function call with a goto back to the beginning of the function.
(This is just you writing the goto that the compiler would, if it supported tail recursion.)

Upvotes: 0

Markus
Markus

Reputation: 113

To show that it's not tail-recursive a transformation might help:

static int fib_tail_helper(int n, int result) {
    if (n == 0) {
        return result;
    }   
    else if (result == 0) {
        return fib_tail_helper(n - 1, result + 1);
    }
    else {
        int tailrecursivePreventingValue = fib_tail_helper(n - 1, 0);
        return fib_tail_helper(n - 1, result + tailrecursivePreventingValue);
    }
}

It does exactly the same as your code but introduces an explanatory variable. You can see that there are 2 calls to fib_tail_helper() in the last else-block. This means exponential running time since the second value depends on the first one.

Upvotes: 1

ArunasR
ArunasR

Reputation: 2005

No it is not tail-recursive.

The compiler needs to evaluate the fib_tail_helper argument first, which means it will create n-1 call stacks before it proceeds to call the last fib_tail_helper as the return value.

Upvotes: 2

Related Questions