fibonacci series


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in ruby

Tags

recursion

Source Code

# Fibonacci recurrence relation:
#   fib(0) = 0
#   fib(1) = 1
#   fib(n) = fib(n-1) + fib(n-2)

# This is the recursive version of the Fibonacci series
# It does not use tail-call optimisation, since that
# would complicate the basic algorithm
def fib(n)
    if n < 2
        return n
    else
        return fib(n-1) + fib(n-2)
    end
end

# This is the tail-call optimizabel version
# of the fibonacci series.
#
# Note: Tail-call optimization is not
# supported in all Ruby implementations.
def fib_tco(n, a=0, b=1)
    if n == 0
        a
    else
        fib_tco(n-1, b, a+b)
    end
end

# This implemenation does not rely on recursion,
# which makes it optimal for large values of n,
# since you can't cause a stack overflow.
# The only limit you have is the maximum int value you can have.
def fib_loop(n)
    a, b = 0, 1

    while n != 0
        a, b = b, a+b
        n -= 1
    end
    # No return neccessary, since Ruby
    # returns the last evaluated expression
    a
end
require 'rspec'
require './fib'

describe '#fib(n)' do
  context 'When given 0' do
    let(:value) { fib(0) }

    it 'returns 0' do
      expect(value).to eq 0
    end
  end

  context 'When given 33' do
    let (:value) { fib(33) }

    it 'returns 3524578' do
      expect(value).to eq 3524578
    end
  end
end

describe '#fib_tco(n, a=0, b=1)' do
  context 'When given 0' do
    let(:value) { fib_tco(0) }

    it 'returns 0' do
      expect(value).to eq 0
    end
  end

  context 'When given 33' do
    let(:value) { fib_tco(33) }

    it 'returns 3524578' do
      expect(value).to eq 3524578
    end
  end
end

describe '#fib_loop(n)' do
  context 'When given 0' do
    let(:value) { fib_loop(0) }

    it 'returns 0' do
      expect(value).to eq 0
    end
  end

  context 'When given 33' do
    let(:value) { fib_loop(33) }

    it 'returns 3524578' do
      expect(value).to eq 3524578
    end
  end
end