1

I'm learning about tail recursion, and before I hand in this problem, I'd like a yes / no answer to whether the code snippet is tail recursive or not.

int fib_in(int n, int current, int prev) {
    if (n == 1 || n == 2) { // n = 1 or 2 both gives fib number 1
        return current;
    }
    return fib_in(n - 1, current + prev, current); // recursive call, current gets updated and new prev is the current, so were going backwards if that makes sense
}

int fib(int n) {
   return fib_in(n, 1, 1); // 1 and 1 is the 2 first fib numbers so theyll be used as base cases
}

int main(void) {
    int n, f;
    printf("the nth number: ");
    scanf("%d", &n);

    // call fib function
    f = fib(n);
    printf("%d \n", f);
    return 0;
}

I definitely think it is, but I made this function in response to another homework assignment, before we learned about tail recursion, so I would've used a technique I didn't know existed. Which is why I'm kinda confused.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Drax
  • 141
  • 8
  • 1
    It's worth remembering that C doesn't require compilers to actually turn tail recursive functions into a loop, unlike, say, scheme. They *can* do tail call optimization, of course, and sometimes do, but it's not a given. – Shawn Nov 18 '19 at 01:18

2 Answers2

5

This answer does a pretty good job of explaining what tail recursion is. Particularly note:

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of (return (recursive-function params)). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

Look at your code again. Does your code fit this description?

CH.
  • 556
  • 1
  • 5
  • 16
4

Yes, it is tail recursive. fib_in() calls itself and doesn't perform any additional computations before returning.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578