jrliv
6/26/2017 - 10:56 PM

Example of how to optimize a recursive method using memoization. From Fundamentals of Computer Programming with C# http://www.introprogrammi

Example of how to optimize a recursive method using memoization. From Fundamentals of Computer Programming with C# http://www.introprogramming.info/wp-content/uploads/2013/07/Books/CSharpEn/Fundamentals-of-Computer-Programming-with-CSharp-Nakov-eBook-v2013.pdf

RecursiveFibonacciMemoization.cs
content_copyfile_download
static long[] numbers;

static void Main()
{
  Console.Write("n = ");
  int n = int.Parse(Console.ReadLine());
  
  numbers = new long[n + 2];
  numbers[1] = 1;
  numbers[2] = 1;

  long result = Fib(n);
  Console.WriteLine("fib({0}) = {1}", n, result);
}

static long Fib(int n)
{
  if (0 == numbers[n])
  {
    numbers[n] = Fib(n - 1) + Fib(n - 2);
  }
  
  return numbers[n];
}

//  n = 100
//  fib(100) = 3736710778780434371