Fibonacci program does not complete execution

Question

Problem Description

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms

Program

using System;

class fibonacci {
    // function to return Nth value of fibonacci
    public static long fibo_n(long N) {
        long fibon=0;
        switch (N) {
            case 1: fibon=1; break;
            case 2: fibon=2; break;
        }
        while(N>2) {
        fibon=fibo_n(N-1)+fibo_n(N-2);
        }
    return fibon;
    }
}    

class fibo_tester {
    static void Main() {
        int N=2;
        long sum=0;
        while(fibonacci.fibo_n(N) <= 13) {
            sum = sum + fibonacci.fibo_n(N);
            N=N+3;
        }
        Console.WriteLine("Sum is {0}: ", sum);
    }
}

I reduced the number to 13 for testing instead of 4 million, but it still hangs. Could someone please advise?

EDIT 2

switch (N) {
        case 1: fibon=1; break;
        case 2: fibon=2; break;
        default: fibon=fibo_n(N-1)+fibo_n(N-2); break;
    }

Answer 1

 while(N>2) {
        fibon=fibo_n(N-1)+fibo_n(N-2);
        }

Is going to loop indefinitely, N is never updated in the loop. You probably need to remove the While() clause and change it all to return fibo_n(N-1)+fibo_n(N-2); I'm not sure what you are doing with the switch statements, etc. But that should be a start.

I would actually replace it with this (if you want to use the switch):

class fibonacci
{
    // function to return Nth value of fibonacci
    public static long fibo_n(long N)
    {
        switch (N)
        {
            case 0:
                return 0;
            case 1:
                return 1;
            default:
                return fibo_n(N - 1) + fibo_n(N - 2);
        }
    }
}   

You might want to consider storing the values for each value of N in a dictionary or some sort of set so that you can look them up later. Since in your main program it seems like you are going to be looping over the values (successively larger N's that may have already been calculated). I'm not sure what the N+3 is about in your main loop, but you probably are going to miss something there (false assumption of the N-1, N-2 in the recursion perhaps?)

Also, if summing and dependent on your platform and how large of a value you test for (sicne your testing the sum of the first X Fibonacci numbers) you may have to use a ulong or find some other datatype that can handle larger numbers. If I don't change everything from long to ulong on my system, the values wrap around. Fibonacci number can't be negative anyways, so why not use a ulong, or uint64 or something with more bits.

Answer 2

You are using BOTH a loop AND recursion - you'll need to pick one or the other. The problem spot in your code is here:

while (N>2) {
    fibon = fibo_n(N-1)+fibo_n(N-2);
}

In this spot the value of N never actually changes - that happens in the recursive step. One example (not good) way to write this is:

public static long fibo_n(long N) {
    if (N <= 0) return 0;
    if (N == 1) return 1;
    if (N <= 4) return N - 1;

    return fibo_n(N-1) + fibo_n(N-2);
}

Best of luck!

---

Performance Note:

The reason this isn't a good approach is because function calls use memory in C# and they also take time. Looping is always faster than recursion and in this case there isn't a good reason to solve this with recursion (as opposed to a simple loop). I'll leave the code as is so you can compare to what you have, but I think you can find much better better code options elsewhere (although not all of these will be in C#).

Answer 3

Let's say you call your method with N equal to 3.

The switch doesn't do anything.

N is greater than 2, so we go into the while loop. The while loop does something; it computes a value, assigns it to fibon. Then N, since it hasn't changed, is still greater than 2, so we compute it again. It'll still be greater than two, so we compute it again. We never stop computing it.

Every time you assign a value to fibon you should instead be returning that value, because you're done; you have nothing left to compute. There's also no need for the while loop. You never need to execute that code more than once.

Your implementation is also super inefficient. To compute fib(5) you compute fib(4) and fib(3). To Then when computing fib(4) you compute fib(3) [again] and fib(2), when computing fib(3) both times they each compute fib(2) (so that's three times there), and if we do the math we end up seeing that you perform on the order of 2^n computations when computing fib(n). On top of that, you're calling fib n times as you're counting up from zero in your main loop. That's tons and tons and tons of needless work re-computing the same values. If you just have a simple loop adding the numbers together as you go you can compute the result with on the order of N computations.