...

/

Tabulating Fibonacci Numbers

Tabulating Fibonacci Numbers

Explore how tabulation can improve the efficiency of finding the nth Fibonacci number.

The tabulation approach is like filling up a table from the start. Let’s now find the nthn^{th} Fibonacci number using bottom-up tabulation. This approach uses iteration and can essentially be thought of as recursive in reverse.

Tabulated version 1

Have a look at the tabulated code in C#:

using System;
class Program
{
/// <summary>
/// Finds the nth Fibonacci number.
/// </summary>
/// <param name="num">An integer number.</param>
/// <param name="lookupTable">Stores already calculated fibonacci number.</param>
/// <returns>The nth Fibonacci number.</returns>
public static int Fib(int num, int[] lookupTable)
{
// Set 0th and first values
lookupTable[0] = 0;
lookupTable[1] = 1;
for (int i = 2; i <= num; i++)
{
// Fill up the table by summing up previous two values
lookupTable[i] = lookupTable[i - 1] + lookupTable[i - 2];
}
return lookupTable[num]; // Return the nth Fibonacci number
}
// Driver code to test above function
public static void Main(string[] args)
{
int num = 6;
int[] lookupTable = new int[num + 1];
Console.WriteLine(Fib(num, lookupTable)); // Output: 8
}
}

This algorithm does the following:

  • Initializes a lookup table and sets the values of Fib(0) and Fib(1), as those are the base cases on lines 14–15.
  • Finds out the values of the rest of the Fibonacci numbers by summing up the values of the previous two (line 20).

The following lines explain how the code works:

fib(0)=0fib(0) = 0 ...