Print fibonacci numbers up tp 15,000 C#

Question

I have seen similar questions(but in C) -- Calculating Fibonacci Numbers Recursively in C about my issue.

I am a bit stuck on how to keep on printing fibonacci numbers until it reaches about 40,000, in C# in my console application, How can I achieve this?

E.G, I want the application to do this:

0
1
1
2
3
5
8

and so on.

Thanks. I'd hate to say this, but I had a brainwave, and solved it!

Here is what I did:

static void Main(string[] args)
{
    int num1 = 0;
    int num2 = 1;
    int sum = 1;
    while (num1 <= 15000)
    {
        sum = num1 + num2;
        num1 = num2;
        num2 = sum;
       Console.WriteLine(num2);
    }
    Console.ReadLine();
}

Answer 1

Just for fun, thought I'd throw in a fun way to do this with LINQ extension methods and a generator (infinite sequence):

// A utility class that holds math utility functions.
public static class MathUtility
{
    // This method returns the fibonacci sequence which is an 
    // infinite sequence of numbers where each result is the
    // sum of the previous two results.
    public static IEnumerable<int> GetFibonacciSequence()
    {
        int first = 0;
        int second = 1;

        // first and second result are always 1.
        yield return first;
        yield return second;

        // this enumerable sequence is bounded by the caller.
        while(true)
        {
            int current = first + second;
            yield return current;

            // wind up for next number if we're requesting one
            first = second;
            second = current;
        }
    }
}

This generates an infinite (theoretically) sequence (it will eventually overflow if you let it go past range of int).

You can then call:

foreach(var num in MathUtility.GetFibonacciSequence().TakeWhile(num => num <= 40000))
{
    Console.WriteLine(num);
}

In this way, you have your presentation (the output) separate from the data generation.

Answer 2

How about something that has a loop in it? Like:

    static void main() 
    {
        int num1 = 0;
        int num2 = 1;
        int sum = 1;
        Console.WriteLine(num1);
        while (sum < 40000)
        {
           sum = num1 + num2;
           num1 = num2;
           num2 = sum;    
           Console.WriteLine(num2);
        }
    }   

Answer 3

static int Fibonacci(int n)
{
    if(n <= 1) return n;
    else return Fibonacci(n - 1) + Fibonacci(n - 2);
}


static void PrintAllFibonacci()
{
    int n = 0;
    while(true)
        Console.WriteLine(Fibonacci(n++));
}

EDIT:

a different approach using a stack

static ulong Fibonacci(int n, IList<ulong> stack)
{
    ulong fibonacci;

    if (n <= 1)
    {
        fibonacci = (ulong)n;
    }
    else
    {
        ulong n1, n2;
        if (n < stack.Count)
            n1 = stack[n - 1];
        else
            n1 = Fibonacci(n - 1, stack);
        if (n - 1 < stack.Count)
            n2 = stack[n - 2];
        else
            n2 = Fibonacci(n - 2, stack);

        fibonacci = n1 + n2;
    }

    if (n >= stack.Count)
        stack.Add(fibonacci);

    return fibonacci;
}


static void PrintAllFibonacci()
{
    var stack = new List<ulong>();
    var n = 0;
    while(n < 50)
        Console.WriteLine(n + ") " + Fibonacci(n++, stack));
}

Answer 4

You can't do that recursively - remember, that each method call uses you stack. Google about, huh, stack overflow :)

You'll need to find iterating version of the algorithm, it's everywhere on the internet. And, of course, while fib numbers are quite quickly running up, it's impossible to output them forever.

Answer 5

Use the Closed form solution

    public static long ClosedFormFibonacci(int i)
    {
        const double phi = 1.61803398874989; // or use your own or calculate it
        const double sqrt5 = 2.23606798; // same as above
        return (long)Math.Round(Math.Pow(phi, i) / sqrt5);
    }

It looks like it overflows a long at about the 92nd Fibonacci number

Answer 6

C# doesn't easily support tail recursion so doing a simple recursion algorithm will cause a stack overflow with large enough numbers. For this problem it would be simplest to use a loop instead of recursion. If you're really stuck on recursion, here is a blog post that investigates both faking recursion and converting C# generated IL code to use tail recursion.

Answer 7

There are 2 major mistakes in your program:

1. Multiple use of main()
2. fibonacci_recursive is not created, though it is declared at the start of program.