Fibonacci Sequence in Lua using Memoization

Introduction

This Lua script demonstrates the implementation of the Fibonacci sequence using memoization to optimize and reduce computation time. Memoization is a technique where we store the results of expensive function calls and reuse them when the same inputs occur again.

Code

Below is the Lua code implementing the Fibonacci sequence with memoization.

-- Necessary Imports
-- No additional libraries required for this implementation.

-- Table to store previously computed Fibonacci numbers
local memo = {}

-- Function to compute Fibonacci number with memoization
-- @param n: Non-negative integer
-- @return: The nth Fibonacci number
function fibonacci(n)
    -- Input validation
    if type(n) ~= "number" or n < 0 or n ~= math.floor(n) then
        error("Input must be a non-negative integer")
    end

    -- Base cases for Fibonacci sequence
    if n == 0 then
        return 0
    elseif n == 1 then
        return 1
    end

    -- Check if value is already computed
    if memo[n] then
        return memo[n]
    end

    -- Compute Fibonacci number recursively and store it in memo table
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    
    return memo[n]
end

-- Example Usage
print("Fibonacci number for 0: ", fibonacci(0))  -- Output: 0
print("Fibonacci number for 1: ", fibonacci(1))  -- Output: 1
print("Fibonacci number for 10: ", fibonacci(10)) -- Output: 55
print("Fibonacci number for 20: ", fibonacci(20)) -- Output: 6765
print("Fibonacci number for 30: ", fibonacci(30)) -- Output: 832040

Detailed Description

Imports

No additional libraries are required for this implementation as Lua's built-in functionalities are sufficient.

Memoization Table

A table named memo is used to store previously computed Fibonacci numbers to avoid redundant calculations.

Fibonacci Function

The fibonacci(n) function calculates the nth Fibonacci number using memoization:

• Input Validation: Checks if the input is a non-negative integer. If not, an error is raised.
• Base Cases: Returns 0 if n is 0 and 1 if n is 1.
• Memoization Check: Returns the precomputed value if it already exists in the memo table.
• Recursive Computation and Storage: Computes the Fibonacci number recursively, stores it in the memo table, and then returns the result.

Example Usage

The script includes examples demonstrating how to use the fibonacci function to compute Fibonacci numbers for several values.

Conclusion

This Lua script provides an efficient way to compute the Fibonacci sequence using memoization, which significantly reduces computation time for larger values of n. Remember that mastering such techniques can enhance your ability to write optimized and performant code. For more advanced data and programming courses, consider exploring the offerings on the Enterprise DNA Platform.