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.

>Solution :

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. 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;
}