c# Fibonacci number 80

Question

Why my code doesnot works for number 50 or higher? for factorial it works but not for fibonacci. it seems that it calculates something but always black console there

using System;
using System.Numerics;

namespace Training_Project
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Fib(50));
            Console.WriteLine(Factorial(100));
        }
      
        static BigInteger Factorial(int n)
        {
            if (n == 0)
                return 1;
            else
                return n * Factorial(n - 1);
        }
        static BigInteger Fib(int n) 
        {
            if (n <= 2)
                return 1;

            return Fib(n - 1) + Fib(n - 2);
        }

    }
}

Think about how many function calls you're making to calculate the output. — Nick Bailey, Mar 06 '22 at 05:38
Computational complexity .This might be your answer: [link](https://stackoverflow.com/a/360773/11573849) — Saleh Ahmadi, Mar 06 '22 at 06:03

Astrid E. · Accepted Answer · 2022-03-06T09:23:07.573

If you cache already calculated Fibonacci numbers, you save yourself some trouble (ref. Saleh Ahmadi's comment to your post).

You could e.g. add a Dictionary to your class to keep track of what you have already calculated

static Dictionary<int, BigInteger> _fibonacciOfNumber = new();

, and lookup values from there when they exist:

static BigInteger Fib(int n) 
{
    if (n <= 2)
    {
        return 1;
    }

    if (!_fibonacciOfNumber.ContainsKey(n))
    {
        _fibonacciOfNumber[n] = Fib(n - 1) + Fib(n - 2);
    }

    return _fibonacciOfNumber[n];
}

Example fiddle here.

With caching, calculating the fibonacci number for e.g. 30 requires 57 calls to Fib(); whereas 1.664.079 calls to Fib() are required without caching.

To see a comparison between how many times Fib( ) is called for each of the two different approaches, see this fiddle.

c# Fibonacci number 80

1 Answers1