We can optimize the recursive method for calculating the Fibonacci numbers by remembering (saving) the already calculated numbers in an array and making recursive call only if the number we are trying to calculate has not been calculated yet. Thanks to this small optimization technique (also known in computer science and dynamic optimization as memoization (not to be confused with memorization) the recursive solution would work for linear count of steps.
Here is a sample implementation:
Exercise 1:
C# Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace test { class Program { static long[] numbers; static long Fib(int n) { if (0 == numbers[n]) { numbers[n] = Fib(n - 1) + Fib(n - 2); } return numbers[n]; } 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); Console.ReadKey(); } } } |
Output:
Exercise 2:
Write a program in C# Sharp to find the Fibonacci numbers for a n numbers of series using recursion. (For example user enters 5, then method calculates 5 fibonacci numbers c# )
C# Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace test { class Program { public static int FindFibonacci(int n) { int p = 0; int q = 1; for (int i = 0; i < n; i++) { int temp = p; p = q; q = temp + q; } return p; } static void Main() { Console.WriteLine("\n\n Recursion : Find the Fibonacci numbers for a n numbers of series :"); Console.WriteLine("-----------------------------------------------------------------------"); Console.Write(" Input number of terms for the Fibonacci series : "); int n1 = Convert.ToInt32(Console.ReadLine()); Console.Write("\n The Fibonacci series of {0} terms is : ", n1); for (int i = 0; i < n1; i++) { Console.Write("{0} ", FindFibonacci(i)); } Console.ReadKey(); } } } |
Output:
