0
\$\begingroup\$

I have created a program that prints the Nth term of the Fibonacci sequence. The fib function needs to use tail recursion. If what I have coded isn't tail recursion, I would like to know how to change the fib function so it does.

#include <iostream>
#include <sstream>

int fib(int n, int i = 0, int a = 0, int b = 1)
{   
    return (i >= n - 1) ? a : fib(n, i + 1, b, a + b);
}

int main(int argc, char* argv[])
{
    if (argc < 2) {
        std::cerr << "Argument 2 must be the Nth term." << std::endl;
        return -1;
    }

    std::stringstream ss_obj(argv[1]);
    unsigned long int number;

    ss_obj >> number;

    std::cout << "\nFibonacci number: " << fib(number) << std::endl;
    return 0;
}
\$\endgroup\$
9
  • 3
    \$\begingroup\$ @vnp because OP is wishing a specific feature, this is, to rewrite the code for tail recursion and this is not a code writing service. It's ok to ask for general improvements about something but not to rewrite it in any special way. And seeing your answer OP doesn't even know what their code is doing since apprently it's using this already. \$\endgroup\$ Commented Nov 3, 2018 at 17:54
  • 2
    \$\begingroup\$ Same thing, different name... \$\endgroup\$ Commented Nov 3, 2018 at 17:57
  • 2
    \$\begingroup\$ @t3chb0t I read the question in an entirely different way. It asks Is it a tail recursion?. Of course you may interpret how to change as a rewrite request; I do not. \$\endgroup\$ Commented Nov 3, 2018 at 17:57
  • 1
    \$\begingroup\$ why exactly do you think that what you have there isn't tail recursion? \$\endgroup\$ Commented Nov 3, 2018 at 18:44
  • 1
    \$\begingroup\$ @Mast: Yes, it matters. Tail recursion can be optimized out, other recursion cannot. \$\endgroup\$ Commented Nov 3, 2018 at 20:41

2 Answers 2

Reset to default
3
\$\begingroup\$

To address your immediate concerns, it is a tail recursion indeed. OTOH, there is no need to be that terse. You may want to be a little more explicit:

    if (i == n) {
        return a;
    }
    return fib(n, i + 1, b, a + b);

Now the tail-recursiveness is obvious.

The error message "Argument 2 must be the Nth term." is misleading. The Nth term definitely refers to the Nth Fibonacci number, rather than the index of the number to be computed.

Besides that, traditionally such message is formatted as

    "Usage: " << argv[0] << " index\n";
\$\endgroup\$
1
  • \$\begingroup\$ If you want to be less terse, use whitespace. No need to shun the ternary operator, it isn't evil. \$\endgroup\$ Commented Nov 4, 2018 at 15:17
2
\$\begingroup\$

Yes, your code is tail-recursive. But C++ does not guarantee tail-call-optimization, so better pray your implementation does it as a matter of Quality of Implementation at your chosen optimization-level anyway.
On second thought, it probably doesn't matter if it doesn't, as you will likely have Undefined Behavior due to integer-overflow before you use up your stack.

  1. Your error-message when called without argument ("Argument 2 must be the Nth term.") is confusing. Use something along these lines:

    Error: You forgot to say which Fibonacci-number you want.

Usage: PROGRAM index

    Or try to fall back to reading from standard input.

  2. You use std::endl twice. Both times, the explicit flush is useless make-work:

    1. std::cerr does not buffer anyway.
    2. Returning from main() leads to normal termination, which includes flushing of std::cout.

  3. Using std::stringstream to parse a single unsigned long is severe overkill.
    std::strtoul() should suffice.

  4. return 0; is implicit for main().

  5. i >= n - 1 is quite a contortion. Why not the simpler i > n?

  6. You only really need three of the four arguments for fib():

    int fib(int n, int i = 0, int a = 0, int b = 1)
{   
    return (i >= n - 1) ? a : fib(n, i + 1, b, a + b);
}

    Can be modified to the more efficient:

    int fib(int n, int a = 0, int b = 1) {
    return 0 > n ? a : fib(n - 1, b, a + b);
}

  7. Anyway, using default-arguments is actually not a good idea, as it costs the caller. Simply use an intermediate which only accepts n:

    static int fib_impl(int n, int a, int b) ...
int fib(int n) {
    return fib_impl(n, 0, 1);
}

  8. If you for some reason think that simple use of the conditional operator is too complicated, use whitespace:

    int fib(int n, int a = 0, int b = 1) {
    return 0 > n
        ? a
        : fib(n - 1, b, a + b);
}
\$\endgroup\$