So I have made 2 versions of Fibonacci calculator, one is in normal way and one is in recursion.

    public static int Fib(int n)
    {
        if (n == 0) { return 0; }
        if(n == 1) { return 1; }
        int a = 0;
        int b = 1;
        int res = 0;
        for (int i = 0; i <= n-1; i  )
        {
            res = a   b;
            a = b;
            b = res;

        }
        return res;
    }

    public static int FibRec(int n)
    {
        if((n == 0) || (n == 1)) { return n; }
        else
        {
            return FibRec(n-1)   FibRec(n-2);
        }
    }

When i run both the same time, the recursive version is incorrect.

static void Main()
    {
        Console.WriteLine(Fib(7)); //return 21
        Console.WriteLine(FibRec(7)); //return 13
    }

I tried to check for a correct version ones on the internet but strangely all the answer is quite the same as mine. I'm very weak at recursive and I absolutely have no idea what wrong with, so I'd be very grateful if any expert can point out the problem.

CodePudding user response：

Your loop in Fib is incorrect in terms of the number of iterations - and this isn't helped by using non-descript names. FibRec is correct, contrary to your assertion in the question. Note that one way of determining that is to print out (say) the first 10 values of the sequence, which I'd expect to be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. That helps to find where the problem starts.

I would advice using current (as in, the current result) and next (the next number), and looping n times. That way you don't even need the base conditions, because it all just drops out. You also don't need to keep three variables outside the loop - you can just introduce a third variable inside the loop instead:

static int Fib(int n)
{
    int current = 0;
    int next = 1;
    for (int i = 0; i < n; i  )
    {
        int tmp = current   next;
        current = next;
        next = tmp;
    }
    return current;
}

Note that deconstruction assignment in modern C# allows you to write it even more clearly, reassigning both current and next in a single statement, based on the previous values:

static int Fib(int n)
{
    int current = 0;
    int next = 1;
    for (int i = 0; i < n; i  )
    {
        (current, next) = (next, current   next);
    }
    return current;
}

CodePudding user response：

Your case base should return 1, not n

public static int FibRec(int n)
{
    if((n == 0) || (n == 1)) { return 1; }
    else
    {
        return FibRec(n-1)   FibRec(n-2);
    }
}

CodePudding user response：

When i run both the same time, the recursive version is incorrect.

Fibonacci(7) is 13, so your recursive FibRec method is correct.

I absolutely have no idea what wrong with

There is nothing wrong with it.

I'd be very grateful if any expert can point out the problem.

There is no problem.

There are only some possible stylistic improvements: you could protect against a caller passing a negative number as an argument and you could use a guard clause or a conditional expression.

If you change the condition to n <= 1 or n < 2, then FibRec will not run into an infinite loop if a caller passes a negative number. While that is an elegant way of solving the problem, FibRec will return a wrong result in that case. A better way would be to throw an appropriate Exception, in particular an ArgumentOutOfRangeException in that case:

if (n < 0)
    throw new ArgumentOutOfRangeException(
        nameof(n),
        n,
        "Argument must be non-negative."
    );

Since throw terminates the method, there is no need for an else. The rest of the method will only be executed if the argument value is valid.

The same applies to return: if you return from the method, the rest of the method will not be executed, therefore, it is not necessary to wrap the rest of the method into an else branch:

public static int FibRec(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(
            nameof(n),
            n,
            "Argument must be non-negative."
        );

    if (n < 2) return n;
    return FibRec(n-1)   FibRec(n-2);
}

This is sometimes called a guard clause.

Alternatively, you could use a conditional expression:

public static int FibRec(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(
            nameof(n),
            n,
            "Argument must be non-negative."
        );

    return n < 2 ? n : FibRec(n-1)   FibRec(n-2);
}

In your original version, where you had no error checking, you could then also use an expression-bodied method:

public static int FibRec(int n) =>
    n < 2 ? n : FibRec(n-1)   FibRec(n-2);

But in this case, you lose the error checking.

See this .NET Fiddle with all the different variants.