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\$

closed as off-topic by πάντα ῥεῖ, t3chb0t, Quill, Toby Speight, Abbas Nov 5 '18 at 22:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – πάντα ῥεῖ, t3chb0t, Quill, Toby Speight, Abbas
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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\$ – t3chb0t Nov 3 '18 at 17:54
  • 2
    \$\begingroup\$ Same thing, different name... \$\endgroup\$ – t3chb0t Nov 3 '18 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\$ – vnp Nov 3 '18 at 17:57
  • 1
    \$\begingroup\$ why exactly do you think that what you have there isn't tail recursion? \$\endgroup\$ – Vogel612 Nov 3 '18 at 18:44
  • 1
    \$\begingroup\$ @Mast: Yes, it matters. Tail recursion can be optimized out, other recursion cannot. \$\endgroup\$ – Cris Luengo Nov 3 '18 at 20:41
4
\$\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\$
  • \$\begingroup\$ If you want to be less terse, use whitespace. No need to shun the ternary operator, it isn't evil. \$\endgroup\$ – Deduplicator Nov 4 '18 at 15:17
3
\$\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\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.