I need to convert this recursive function into tail recursive function but i am getting the wrong output can any help me out with this.

Here is the function definition:

f(n) = 3f(n − 1) - f(n − 2) n, with initial conditions f(0) = 1 and f(1) = 2.

#include <iostream>

using namespace std;

int headRecursion(int n) {
    if(n == 0) {
        return 1;
    }

    if (n == 1) {
        return 2;
    }

    return 3 * headRecursion(n - 1) - headRecursion(n - 2)   n;
}

int main(){
    cout << endl << headRecursion(3);
    return 0;
}

CodePudding user response：

This is kind of an interesting problem. We can start with how to implement as a loop:

int minus2 = 1;
int minus1 = 2;

if (n == 0) return minus2;
if (n == 1) return minus1;
for( int i = 2; i <= n; i  )
{
    int next = minus1 * 3 - minus2   i;
    minus2 = minus1;
    minus1 = next;
}
return minus1;

The takeaway is we need to count UP. In order to make this tail recursive we need to pass in our accumulators (there is no reason to do this other than to show off, but it adds nothing to readability or efficiency)

int tailRecursive(int minus2, int minus1, int step, int n)
{
    if (step == n) return minus1;
    return tailRecursive(minus1, minus1*3 - minus2   step 1, step 1, n);
}

you can use an intermediate to set it up and handle the n==0 case.

int calcIt(int n) {
    if (n == 0) return 1;
    // step must start with 1, since we handled 0 above
    return tailRecursive(1, 2, 1, n);
}

CodePudding user response：

Something along these lines:

std::pair<int, int> next_result(std::pair<int, int> prev_result, int n) {
  return {3*prev_result.first - prev_result.second   n, prev_result.first};
}

std::pair<int, int> tailRecursion(int n) {
    if (n == 0) {
        return {1, 0};
    }
    if (n == 1) {
        return {2, 1};
    }
    return next_result(tailRecursion(n-1), n);
}

int compute(int n) {
    return tailRecursion(n).first;
}

int main(){
    std::cout << compute(3) << std::endl;
}

Demo

The key is that you need a function that computes a pair {f(n), f(n-1)} given the previously computed pair {f(n-1), f(n-2)}