Programming Fun With Fibonacci Numbers

When you are learning about recursive functions in programming, two examples from mathematics are used to teach the concept: calculating factorials and the Fibonacci sequence.

Let's look at Fibonacci.  The sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

So, the first two values are: fib(0) = 0, fib(1)=1

After that, the next fib number is the sum of the previous two,  So, fib(2) = fib(0) + fib(1), fib(3) = fib(2) + fib(1), etc.

I saw an online discussion of someone wanting to sum the first N Fibonacci sequence, and looking for an efficient recursive program.

I wondered if you even needed recursion for the sum since, when you are summing integers, you can do it without a loop or recursion.  The sum of the first N integers is N(N+1)/2

So, I dug in and found that you can sum the first N Fibonacci numbers without loops or recursion.

1. First, we can define the constant phi =  (1 + sqrt(5))/2   #1 plus the square root of 5, divided by 2

2. Next, we can create a function to calculate the nth Fibonacci number without loops or recursion:

fib(n) =  int_round_up {[ phi ^ n - (-1 / phi) ^ n ] / sqrt(5) }  # do the calc in decimal and round up to int

3.  Finally, the function to find the sum of the first N Fibonacci numbers:

Sum_fib(n) = fib(n+2) - 1  # The sum of the first N Fib numbers is just the N+2 Fib number - 1

So, it turns out finding the sum of Fibonacci numbers is actually a simple, elegant process.

© 2024 Praveen Puri