Different ways to calculate the Fibonacci sequence to illustrate good recursion and bad recursion.

fib.rb

class Fibonacci
    # really bad recursive fibonacci
    def fib_at(n)
        if n == 0
            return 0
        elsif n == 1  
            return 1
        else
            # we are calculating the same values over and over again!
            return fib_at(n - 1) + fib_at(n - 2)
        end
    end

    # same recursive call but we cache our calculations 
    def memoized_fib_at(n)
        # create a cache of results if not created 
        @fib_results ||= Array.new

        if n == 0
            return 0
        elsif n == 1
            return 1
        else
            # is the result calculated already?
            value = @fib_results[n]
            return value unless value.nil?
        
            # perform the same recursion 
            value = memoized_fib_at(n - 1) + memoized_fib_at(n - 2)
            
            # save the result
            @fib_results.insert(n, value) 
            value
        end
    end

    # non recursive iteration
    def non_recursive_fib_at(n)
        return 0 if n == 0
        return 1 if n == 1

        grand_parent = 0
        parent = 1 

        for i in 2 .. n
            current = grand_parent + parent 
            grand_parent = parent
            parent = current
        end

        current
    end 
end

require "test/unit"
class FibonacciTest < Test::Unit::TestCase
    def setup
        @fib = Fibonacci.new
    end

    def test_fib_at
        assert_equal 0, @fib.fib_at(0) 
        assert_equal 1, @fib.fib_at(1)
        assert_equal 1, @fib.fib_at(2)
        assert_equal 2, @fib.fib_at(3)
        assert_equal 3, @fib.fib_at(4)
        assert_equal 5, @fib.fib_at(5)
        assert_equal 8, @fib.fib_at(6)
    end

    def test_memoized_fib_at
        assert_equal 8, @fib.memoized_fib_at(6)
        assert_equal 13, @fib.memoized_fib_at(7)
    end

    def test_non_recursive_fib_at
        assert_equal 8, @fib.non_recursive_fib_at(6)
        assert_equal 13, @fib.memoized_fib_at(7)
    end
end