Fibonacci numbers exploration - 4 ways

Fibonacci numbers are a series of numbers in which each number is the sum of the two numbers before it. As the first two numbers, it starts with 0 and 1. This sequence is a well-known mathematical formula. Fibonacci numbers can be seen in plant and animal structures. These numbers are sometimes known as the universal rule of nature or the secret code of nature. Let’s take a closer look at Fibonacci numbers in this article.

Fibonacci Numbers: What Are They?

Fibonacci numbers are a series of whole numbers that go from 0 through 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. Every number is the sum of the two numbers before it. Here are a few fascinating facts regarding Fibonacci numbers:

This sequence is known as the Fibonacci sequence, and it is endless. The Fibonacci series or sequence is represented by the letters Fn. If we build squares with certain widths, Fibonacci numbers can be represented as a spiral, as illustrated below. We can see how the squares fit together nicely in the diagram. For example, 5 plus 8 equals 13, 8 plus 13 equals 21, and so on.

We will discover 4 ways to find Fibonacci numbers:

1. Using Recursion

The method is a straightforward recursive implementation of the mathematical recurrence relation.

import Foundation

func fibonacci(num: Int) -> Int {

if num <= 1 {

return num

}

return fibonacci(num: num - 1) + fibonacci(num: num - 2)

}

print(fibonacci(num: 7)) // prints 13

Time Complexity: T(n) = T(n) which is linear.

2. Dynamic programming

By saving the Fibonacci numbers determined so far, we may avoid the repetitive labor of approach 1.

func fibonacci(num: Int) -> Int {

var numbers = Array(repeating: 0, count: num + 1)

numbers[0] = 0

numbers[1] = 1

for i in 2...num {

//Add the previous 2 numbers

// in the series and store it

numbers[i] = numbers[i - 1] + numbers[i - 2];

}

return numbers[num]

}

print(fibonacci(num: 7)) // prints 13

3. Optimized for Space Method 2

We can save space by keeping only the previous two numbers in method 2 because that is all we need to get the next Fibonacci number in the series.

func fibonacci(num: Int) -> Int {

var a = 0

var b = 1

var c: Int = 0

for _ in 2...num {

c = a + b

a = b

b = c

}

return b

}

print(fibonacci(num: 7)) // prints 13

Time Complexity:O(n) Extra Space: O(1)

4. Using formula

In this method we directly implement the formula for nth term in the fibonacci series. Fn = {[(√5 + 1)/2] ^ n} / √5

Formula Reference is here.

func fibonacci(num: Int) -> Int {

let phi = (1 + sqrt(5)) / 2

return Int( round(pow(phi, Double(num)) / sqrt(5)) )

}

print(fibonacci(num: 7)) // prints 13

Time Complexity: O(logn), this is because calculating phi^n takes logn time Space Complexity: O(1)

Summary

Fibonacci numbers are a series of whole numbers that go from 0 through 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. These numbers are sometimes known as the universal rule of nature or the secret code of nature. We can save space by keeping only the previous two numbers in method 1, which is all we need to get the next fibonacci number in the series.

Thanks

Much grateful to you for following me and my stories. Happy to have you here, and would like to make it worth your time.