The Fibonacci Sequence as a Solution to Real-Life Problems

There are many problem types that can be asked in technical interviews. Problems related to the Fibonacci sequence are among the most widespread in this category.

Here, we will explore the sequence from both mathematical and engineering perspective, discuss its solutions using both iterative and recursive methods in C and JavaScript languages, and also examine a problem from Leetcode which solution can be derived through the Fibonacci sequence...

The Fibonacci Sequence

The Fibonacci sequence is a range of positive numbers (including 0), where the first number is 0 and the second number is 1. After these initial two numbers, each subsequent number is the sum of the two preceding numbers. For instance, the second number is obtained by adding 0 and 1, resulting in 1. The third number is obtained by adding 1 and 1, resulting in 2, and so on.

The n-th number of the Fibonacci sequence can be calculated using the formula

Fn = Fn-1 + Fn-2

where

F0 = 0 and F1 = 1

The numbers of Fibonacci...

0,1,1,2,3,5,8,13,21,34 ......

Conventionally, Fibonacci numbers begin with 0, so the counting of its members also starts from 0.

The first description of Fibonacci numbers appeared in Indian Mathematics. However, the term 'Fibonacci sequence' was first used by the number theorist Edouard Lucas in the 19th century. This is in honor of the large scale of Fibonacci's exploration and use of this sequence in his book 'The Book of Calculation'.

Here one of the interesting parts about this sequence. When we try to use squares with sides' of fibonacci numbers and connect its opposite squares like in the picture bellow, there will be spiral:

The Fibonacci sequence, with its unique properties of growth and proportion, often manifests in natural patterns and structures, such as the arrangement of leaves on a stem, the petals of a flower, the spirals of a pinecone and even the branching of trees. These patterns have fascinated artists for centuries and have influenced various artistic endeavors.

Additionally, the golden ratio, which is derived from the Fibonacci sequence, is a proportion that is aesthetically pleasing to the human eye. It has been used by artists and architects throughout history to create compositions and designs that are considered visually harmonious.

Here are one sample of usage the golden ratio in the art:

N-th number of Fibonacci: Solutions with C and Javascript languages

As mentioned earlier, computing the n-th Fibonacci number is a common task in technical interviews.

Here, we will solve this problem step by step.

1. If the argument passed to the function is negative we will return -1.
2. For the first three numbers (0 , 1 and 1) of the Fibonacci sequence we will return n
3. And with last step we will use a while loop to compute Fibonacci numbers iteratively until reaching the desired one. During every iteration must be changed our prevNum (initial value is 0), currentNum (initial value is 1) and counted nextNum (initial value 0) variables.

When while loop end its work we will return prevNum, which is the appropriate number of Fibonacci sequence.

Next approach is Recursive way.

In this approach of solution first steps are the same:

1. check is the number negative and return -1 in that case
2. check if it is greater than or equal to 0 and less than 2 simultaniously, return n.
3. and at least during each call return the sum of the results of recursive calls with arguments (n-1) and (n-2). This recursive process continues until 'n' reaches 1 or 2, at which point the function returns 1 to account for the base cases of the Fibonacci sequence. Through this recursive approach, the function effectively computes the Fibonacci sequence by iteratively summing the results of previous calls until it reaches the desired Fibonacci number.

These two approaches differ from each other in terms of both Big O notation and memory usage. Each approach likely has its own computational complexity and memory requirements, which determine its efficiency and scalability. Understanding these differences can help in choosing the most suitable approach for a given problem or system:

Iterative Approach:

• Memory Usage: Iterative approach typically uses a constant amount of memory regardless of the input size. It only requires a few variables to store intermediate results.
• Big O Notation: The time complexity of the iterative Fibonacci algorithm is O(n). It iterates through the loop n times to compute the nth Fibonacci number, making it linear in time complexity.

Recursive Approach:

• Memory Usage: Recursive approach tends to use more memory due to the function call stack. Each recursive call consumes memory until the base case is reached.
• Big O Notation: The time complexity of the recursive Fibonacci algorithm is O(2^n). This is because each recursive call branches into two more calls, resulting in an exponential growth in function calls and time complexity.

So to recap we can say the iterative approach is generally preferred over the recursive approach for computing Fibonacci numbers due to its lower memory usage and better time complexity. The recursive approach can lead to stack overflow errors for large values of "n" due to large memory usage, while the iterative approach is more efficient in terms of both time and memory.

The "Cilmbing Stairs" problem of Leetcode (Number 70)

After becoming familiar with the logic of finding the n-th Fibonacci number, let's solve Leetcode problem number 70. Try to solve it by yourself if you haven't submitted this problem yet. You may already have guessed the algorithm for the solution.

Now my version:

The problem description: "You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?"

There are also examples, which can help us find solutions:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
        

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step        

If you attempt to count all possible steps for each number, you will discover that the range you have forms a Fibonacci sequence. Therefore, you can solve this problem using the algorithm to find the n-th Fibonacci number discussed above.

Here is my sample of submission:

In conclusion, it's worth underlining again that the Fibonacci sequence finds widespread usage in the real world. These numbers are used in various fields such as architecture, art, space exploration, engineering, technology, and computing. In engineering and technology, Fibonacci numbers play a significant role, appearing in population growth models, software engineering, task management, and data structure analysis.