I don't know how to correct my tail recursion (originally regular recursion)

Question

I was assigned funct() and was told to convert it into tail recursion, so I made funct2(). I used another stack overflow thread to begin and it kind of works, but it's always a value off.

I think the problem is due to the y value being 0 initially, and when going to the else part of the function, subtracts from 0 rather than a value that is equivalent to the initial x. But I'm not sure.

#include <iostream>
#include <stdio.h>
using namespace std;
int funct(int x);
int funct2(int x, int y);

int main() {

    int x = 24;

    printf("%d %d", funct(x), funct2(x, 0));


}

int funct(int x) {

    if (x <= 0){
        return 0;
    }
    else if (x & 0x01){
        return x + funct(x-1);
    }
    else {
        return x - funct(x-1);
    }

}

int funct2(int x, int y) {

    if (x < 0){
        return 0;
    }
    else if (x == 0){
        return y;
    }
    else if (x & 0x01){
        return funct2(x-1, y+x);
    }
    else {
        return funct2(x-1, y-(x-1));
    }

}

Any help is appreciated. Thanks guys!

tail recursion isn't a language level feature of C, so if you compiler does something fancy to not increase the stack level for the tail calls... that would be a specific optimization... unless you write it with goto and labels ... which are C level constructs, evil, evil constructs. — Grady Player, Dec 01 '16 at 21:30

score 1 · Answer 1 · edited May 23 '17 at 11:53

Take a look at this great explanation. Since your recursive step is not associative, you cannot achieve tail recursion with just two arguments. Consider passing three:

    int tailrec(int x, int k, int acc)
    {
        if (x < 0) {
            return acc;
        }
        if (k & 0x01) {
            return tailrec(x - 1, k + 1, k + acc);
        } else {
            return tailrec(x - 1, k + 1, k - acc);
        }
    }

I don't know how to correct my tail recursion (originally regular recursion)

1 Answers1