> fib0 <- function(n, verbose=FALSE){
+ if (verbose) cat("n = ", n, " ")
+ if (n <= 2) return(1)
+ fib0(n - 1, verbose=verbose) + fib0(n - 2, verbose=verbose)
+ }
> sapply(1:10, fib0)
[1] 1 1 2 3 5 8 13 21 34 55
I’ve included a verbose argument to trace the recursive function calls (see below).
> fib1 <- function(n){
+ if (n <= 2) return(1)
+ last.minus.1 <- 1
+ last.minus.2 <- 1
+ for (i in 3:n){
+ save <- last.minus.1
+ last.minus.1 <- last.minus.1 + last.minus.2
+ last.minus.2 <- save
+ }
+ last.minus.1
+ }
>
> sapply(1:10, fib1)
[1] 1 1 2 3 5 8 13 21 34 55
> fib2 <- function(n){
+ round(((1 + sqrt(5))/2)^n/sqrt(5))
+ }
> sapply(1:10, fib2)
[1] 1 1 2 3 5 8 13 21 34 55
> options(scipen=10) # suppress scientific notation
> system.time(print(fib0(30)))
[1] 832040
user system elapsed
2.87 0.01 2.89
> system.time(print(fib1(70)))
[1] 190392490709135
user system elapsed
0 0 0
> system.time(print(fib2(70)))
[1] 190392490709135
user system elapsed
0 0 0
The latter two solutions are too fast to time with system.time()
but we can get timings with the microbenchmark package:
> library(microbenchmark) # need to install the microbenchmark package
> microbenchmark(fib1(70))
Unit: microseconds
expr min lq mean median uq max neval
fib1(70) 38.014 43.526 46.84437 45.6165 50.178 68.424 100
> microbenchmark(fib2(70))
Unit: microseconds
expr min lq mean median uq max neval
fib2(70) 1.52 1.521 2.22774 1.9005 1.901 21.288 100
As expected fib2()
, which uses Binet’s formula is much faster (proportionally) than fib1()
, which uses iteration.
fib2(70)
produces the right answer, but not fib2(72)
:
> fib1(71)
[1] 308061521170129
> fib2(71)
[1] 308061521170130
To see why the recursive function fib0()
is so inefficient, trace the computation:
> fib0(8, verbose=TRUE)
n = 8 n = 7 n = 6 n = 5 n = 4 n = 3 n = 2 n = 1 n = 2 n = 3 n = 2 n = 1 n = 4 n = 3 n = 2 n = 1 n = 2 n = 5 n = 4 n = 3 n = 2 n = 1 n = 2 n = 3 n = 2 n = 1 n = 6 n = 5 n = 4 n = 3 n = 2 n = 1 n = 2 n = 3 n = 2 n = 1 n = 4 n = 3 n = 2 n = 1 n = 2
[1] 21
It’s apparent that some of the same Fibonacci numbers (e.g., for n = 2) end up being computed over and over and over again.