Notes for SICP problems in ruby

fast_fibonacci.rb

def fibonacci(n)
  fib_iter(1, 0, n)
end

def fib_iter(a, b, n)
  n == 0 ? b : fib_iter((a+b), a, (n-1))
end

slow_fibonacci.rb

def fibonacci(n)
  n <= 1 ? n :  fibonacci( n - 1 ) + fibonacci( n - 2 )
end

Fibonacci SICP

Above is recursive and inefficient:

The faster version in lisp is:

(define (fib n)
  (fib-iter 1 0 n))


(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

This is iterative rather than recursive.

Each cycle inputs are shifted, and the last number is decremented for example:

fib-iter 1 0 5
fib-iter 1 1 4 ;; First variable is sum of first 2 variables above
fib-iter 2 1 3 ;; Last variable is simply decremented by 1 each time
fib-iter 3 2 2 ;; First variable above is always shifted right, a becomes b
fib-iter 5 3 1
fib-iter 8 5 0 ;; Here 5 is returned

Links

https://web.archive.org/web/20171120112547/https://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html