A331164 Number of function evaluations when recursively calculating Fibonacci(n) with caching.

1, 1, 1, 3, 6, 5, 9, 8, 11, 10, 14, 13, 16, 13, 19, 15, 18, 15, 22, 18, 21, 18, 24, 20, 23, 20, 27, 23, 26, 23, 29, 22, 25, 22, 32, 26, 29, 26, 32, 25, 28, 25, 34, 28, 31, 28, 34, 27, 30, 27, 37, 31, 34, 31, 37, 30, 33, 30, 39, 33, 36, 33, 39

Offset

0,4

Comments

One way to calculate the Fibonacci numbers recursively is to use:

F(0) = 0, F(1) = 1, F(2) = 1,

F(n) = F((n + 1)/2)^2 + F((n - 1)/2)^2 for odd n,

F(n) = F(n/2) * (F(n/2 - 1) + F(n/2 + 1)) for even n.

Proof: It is known that F(i) * F(j) + F(i + 1) * F(j + 1) = F(i + j + 1) (see formula section of A000045).

For even n, let i = n/2 and j = n/2 - 1, for odd n, let i = j = (n + 1)/2.

This table gives the number of evaluations of F for calculating F(n). It is assumed that values of F which have been previously calculated are available; looking up a previously calculated value counts as a function evaluation.

a(0) = 1, a(1) = 1, a(2) = 1,

if (a(n)) has not been previously calculated then

a(n) = a((n + 1)/2) + a((n - 1)/2) + 1, n odd,

a(n) = a(n/2) + a(n/2 - 1) + a(n/2 + 1) + 1, n even,

else

a(n) = 1.

Conjecture: a(n) is O(log n).

Links

Thomas König, Table of n, a(n) for n = 0..10000

Thomas König, Calculation of Fibonacci numbers, Fortran program including operation counts.

Thomas König, Graph for calculating F(10) with different ordering of the calls.

Example

Calculation of F(15) = 15:
Level of recursion is marked with indentation and "level", so calculating F(15) (level 1) calls F(8) (level 2), which calls F(5) (level 3) etc... until a cached value is reached.
F(15) level 1
  F(8) level 2
    F(5) level 3
      F(3) level 4
        F(2) level 5 cached
        F(1) level 5 cached
      F(2) level 4 cached
    F(4) level 3
      F(3) level 4 cached
      F(2) level 4 cached
      F(1) level 4 cached
    F(3) level 3 cached
  F(7) level 2
    F(4) level 3 cached
    F(3) level 3 cached

Prog

(Fortran) program main
  implicit none
  integer, parameter :: pmax = 100000
  integer :: r, n
  logical, dimension(0:pmax) :: cache
  do n=0, pmax
     cache (0:2) = .true.
     cache (3:pmax) = .false.
     r = a(n)
     write (*, fmt="(I0, ', ')", advance="no") r
  end do
  write (*, fmt="()")
contains
  recursive function a (n) result(r)
    integer, intent(in) :: n
    integer :: r
    if (cache(n)) then
       r = 1
       return
    else if (mod(n, 2) == 1) then
       r = a ((n+1)/2) + a ((n-1)/2) + 1
    else
       r =  a(n/2+1) + a (n/2) + a(n/2-1) + 1
    end if
    cache (n) = .true.
  end function a
end program main

Crossrefs

Cf. A000045; see A331124 for the number of evaluations without caching.

Sequence in context: A010620 A046128 A342222 * A057098 A053628 A334717

Adjacent sequences: A331161 A331162 A331163 * A331165 A331166 A331167

Keyword

nonn,easy,hear

Author

Thomas König, Jan 11 2020

Status

approved