homework_for_schemeR.md

fibとfibiterの違い

(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

(define (fibiter a b count) (if (< count 1) b (fibiter (+ a b) a (- count 1)))) 

fib

(fib 4)

(+ 
  (fib 3)
  (fib 2)
)

(+
  (+ 
    (fib 2)
    (fib 1)
  )
  (+
    (fib 1)
    (fib 0)
  )
)

(+
  (+
    (+
      (fib 1)
      (fib 0)
    )
    1
  )
  (+
    1
    0
  )
)

(+
  (+
    (+
      1
      0
    )
    1
  )
  1
)

(+
  (+
    1
    1
  )
  1
)

(+
  2
  1
)

3

fibiter

(fibiter 1 0 4)

(fibiter 1 1 3)

(fibiter 2 1 2)

(fibiter 3 2 1)

(fibiter 5 3 0)

3

計算量 (fib n/fibiter nをやる回数)

n	fib	fibiter
1	1	2
2	3	3
3	5	4
4	9	5
5	15	6
6	25	7
7	41	8
8	67	9
9	108	10
10	176	11

Rubyでfib

def fib(n)
  if n < 2
    n
  else
    fib(n - 1) + fib(n - 2)
  end
end

Rubyでfibiter

def fib(a b count)
  if count < 1
    b
  else
    fib((a + b) a (count -1))
  end
end