FIBONACCI Sequence: Algorithm and Python Implementation Simplified

1.1 The Fibonacci Sequence

The Fibonacci numbers, sometimes known as Fn, create a series in which each number is the sum of the two numbers before it. Although some authors ignore the initial words and begin the sequence from 1 and 1 or from 1 and 2, the pattern typically starts from 0 and 1. The following values follow 0 and 1 in the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...

1.2 The previous two digits are combined to yield the following number:

• The 1 is found by adding the two numbers that precede it (0+1),
• The 2 by adding the two numbers that come before it (1+1),
• The 3 by adding the two numbers that come before it (1+2),
• The 5 by adding the two numbers that come before it (2+3), and so on!

1.3 Mathematically, Fibonacci can be represented by: F(1) = 1 F(2) = 1 F(n) = F(n − 1) + F(n − 2)

1.4 pictorial representation

2 Fibonacci Algorithm

2.1 Non-Recursive Iterative Algorithm for Fibonacci Procedures or subroutines written in a programming language that do not refer to themselves are known as non-recursive functions.

2.1.1 Algorithm non-recursive Fibonacci

Procedure Iterative_Fibonacci(n):
    int f0, f1, fib
    f0 = 0
    f1 = 1
    display f0, f1
    for int i:= 1 to n:
        fib := f0 + f1   
        f0 := f1
        f1 := fib
        display fib
    END for loop
END Iterative_Fibonacci

2.1.2 Python implementation

num_terms = int(input("Number of terms? "))

# first two terms
f1, f2 = 0, 1
count = 0

# checking for the validity of the number of terms
if num_terms <= 0:
   print("Enter a positive integer")
# if there is only one term, return f1
elif num_terms == 1:
   print("Fibonacci sequence to",num_terms,":")
   print(f1)
# generate fibonacci sequence
else:
   print("Fibonacci sequence:")
   while count < num_terms:
       print(f1)
       nths = f1 + f2
       # update values
       f1 = f2
       f2 = nths
       count += 1

2.2 Recursive implementation of the Fibonacci sequence

Recursion is a powerful programming concept that provides an effective way to solve large problems by breaking them down into simpler subproblems, using this approach, it's often possible to unravel seemingly complex problems via repeated application of very simple solutions to the subproblems. When we speak about recursion in programming, we are simply talking about recursive functions. A recursive function is a function that calls itself somewhere in its definition, The function is defined in terms of itself.

2.2.1 Properties of Recursion

1. There must be a reachable base case where the function stops calling itself otherwise infinite loop will occur
2. The argument of the function must be modified with each call.
3. Performing the identical operations multiple times with different inputs.
4. For each step, we apply smaller inputs to reduce the complexity of the problem.

2.2.2 Algorithm of Recursive Fibonacci

START
Procedure Fibonacci(n)
   declare f0, f1, fib, loop 

   set f0 to 0
   set f1 to 1

   display f0, f1

   for loop ← 1 to n

      fib ← f0 + f1   
      f0 ← f1
      f1 ← fib

      display fib
   end for

END

2.2.3 Python implementation

def fibo(n):
   if n <= 1:
       return n
   else:
       return(fibo(n-1) + fibo(n-2))

nterms = int(input('enter an integer? '))

# check if the number of terms is valid
if nterms <= 0:
   print("Please enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(recur_fibo(i))

Thanks for reading, kindly follow for more interesting content on Data structure and Algorithm