tail recursive version of the fibonacci function

Question

I am having trouble understanding the concept of tail recursion, I want to make a tail recursive version of the fibonacci function and so far this is what I came up with but I don't know if its correct or not,can someone help me out, any help would be appreciated

#include <stdio.h>

int fibonacci(int n)
{
    if(n==1)return 1;
    if(n==2)return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}


int fibonacci_tail_Recusive(int n,int prev1,int prev2)
{
    
    if(n<0) return -1;
    if(n==1||n==0) return prev2;
    return fibonacci_tail_Recusive(n-1,prev2+prev1,prev1);
}

int fibonacci_tail_Recusive_wrapper(int n)
{
    return fibonacci_tail_Recusive(n,1,1);
}


int main()
{
    printf("tail recursive result: %d  normal recursive result:%d", fibonacci_tail_Recusive_wrapper(23) ,fibonacci(23));

    return 0;
}

the code compiles and outputs the correct result

Answer 1

int fibonacci_tail_Recusive(int n,int prev1,int prev2)
{
    
    if(n<0) return -1;
    if(n==1||n==0) return prev2;
    return fibonacci_tail_Recusive(n-1,prev2+prev1,prev1);
}

This function is, correctly, tail-recursive.

A tail-recursive function is one where all the paths end (i.e., return) either a value (-1 for negative, prev2 for 1 and 0) or a call to a function (it doesn't need to be itself directly; though if it doesn't call itself either directly or indirectly it wouldn't be tail-recursive).

Fibonacci isn't a great example to show tail-recursion because here it muddles the benefit of tail-recursion (being equivalent to an iterative loop) with the optimization of avoiding redundant calls (the original fibonacci function calls itself twice in the final case).

Consider the factorial function:

int factorial(int n)
{
    if (n == 0 || n == 1) return 1;
    return factorial(n - 1) * n;
}

When you call factorial(5), the call stack looks like this:

factorial(5)
   5 * factorial(4)
   5 * (4 * factorial(3))
   5 * (4 * (3 * factorial(2)))
   5 * (4 * (3 * (2 * factorial(1))))
   5 * (4 * (3 * (2 * 1)))
   5 * (4 * (3 * 2))
   5 * (4 * 6)
   5 * 24
   120

at each step, a multiplication is waiting for the next operand so it can calculate its result, meaning each needs to hold some amount of memory for each step.

With the tail-recursive function, like this:

int factorial(int n, int acc)
{
    if (n == 0 || n == 1) return acc;
    return factorial(n - 1, acc * n);
}

the call stack looks like this:

factorial(5, 1);
factorial(4, 5);
factorial(3, 20);
factorial(2, 60);
factorial(1, 120);
120

since at each step the function has finished all the calculations it needs to perform, it doesn't need to hold any memory for the results; each call overwrites the current frame; in other words, it could be rewritten as a loop:

int factorial(int n, int acc)
{
    while (true) {
        if (n == 0 || n == 1) return acc;
        acc = acc * n;
        n = n - 1;
    }
}

If the compiler is smart enough, the code for the tail-recursive function gets converted to the equivalent code that this function would generate.