Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Recursion?
2.1.
Python
3.
Recursion Approach to Find and Print Nth Fibonacci Numbers
3.1.
Python
4.
Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers
4.1.
Python
5.
Nth Power of Matrix Approach to Find and Print Nth Fibonacci Numbers
5.1.
Python
6.
Frequently Asked Questions
6.1.
Why does the simple recursive method for Fibonacci numbers get slow for large inputs?
6.2.
How does dynamic programming improve the calculation of Fibonacci numbers?
6.3.
Why use the matrix method to calculate Fibonacci numbers?
7.
Conclusion
Last Updated: May 1, 2024
Easy

Fibonacci Using Recursion

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It starts with 0 & 1, and then each subsequent number is calculated by adding the two numbers before it. So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. Fibonacci numbers have many interesting mathematical properties & show up in various places in nature. 

Fibonacci Using Recursion

In this article, we'll learn how to calculate Fibonacci numbers using a recursive approach in programming. We'll cover the basic recursive algorithm, look at code examples & discuss some optimizations & alternative approaches.

What is Recursion?

Recursion is a method in programming where a function calls itself to solve a problem. This technique is useful for solving problems that can be broken down into smaller, similar problems. It is like solving a puzzle by first solving smaller parts of it and using those solutions to build up the answer to the entire puzzle.

In recursion, we have a base case and a recursive case. The base case stops the recursion from continuing forever. It is the simplest instance of the problem, which we know the answer to without needing further calculations. For example, the base case in a Fibonacci sequence could be knowing that the first two Fibonacci numbers are 0 and 1.

The recursive case is where the function calls itself. Each call to the function breaks the problem down into a smaller piece, moving closer to the base case.

Let's see how this works with computing Fibonacci numbers. To find the Fibonacci number at a specific position, you add the two Fibonacci numbers before it. Using recursion, we define the function to call itself to find these preceding numbers until reaching the base cases, which are the first two numbers of the sequence.

Here's a basic example in Python to illustrate:

  • Python

Python

def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)

# Example: Find the 5th Fibonacci number
print(fibonacci(5))


Output

5


This code defines a fibonacci function that uses recursion to find the nth Fibonacci number. It uses the base cases of fibonacci(0) returning 0 and fibonacci(1) returning 1. For any other number, it keeps calling itself with the previous two positions until it reaches these base cases.

Recursion can be elegant and straightforward, but it can also lead to performance issues if not used carefully. In the following sections, we'll explore how to implement this approach efficiently.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Recursion Approach to Find and Print Nth Fibonacci Numbers

To demonstrate recursion with a practical example, we'll focus on finding and printing the Nth Fibonacci number. As discussed, the Fibonacci sequence starts with 0 and 1, and every subsequent number is the sum of the two preceding ones. Our task is to write a program that takes a number N and returns the Nth Fibonacci number using recursion.

Here’s how we can implement this in Python:

  • Python

Python

def fibonacci(n):
# Base case: the first two Fibonacci numbers
if n == 0:
return 0
elif n == 1:
return 1
# Recursive case: sum of the two preceding Fibonacci numbers
else:
return fibonacci(n-1) + fibonacci(n-2)

# Example usage: Find the 10th Fibonacci number
print(fibonacci(10))


Output

55

In this example, the fibonacci function calls itself with n-1 and n-2 until it reaches the base cases, which are n == 0 and n == 1. This example clearly shows how the function stacks calls until it reaches the base case, then unwinds the stack to produce the result.

This recursive method is straightforward but can be inefficient for larger values of N due to redundant calculations. For instance, calculating fibonacci(5) requires calculating fibonacci(4) and fibonacci(3), and both of these calculations independently require the calculation of fibonacci(2). As N increases, this redundancy grows exponentially, significantly slowing down the computation.

To address this inefficiency, programmers can use other methods, such as dynamic programming, which we will discuss next. This method stores already computed values to avoid redundant calculations, speeding up the process remarkably.

Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers

Dynamic programming is a technique that improves the efficiency of recursive algorithms by storing results of subproblems so that each subproblem is solved only once. This approach is especially beneficial for problems like Fibonacci, where the same values are calculated multiple times in a simple recursive approach.

To illustrate the dynamic programming approach for the Fibonacci sequence, we can use a method called memoization, which involves creating an array to store the Fibonacci values as they are calculated. Here’s how you can implement this in Python:

  • Python

Python

def fibonacci(n, memo={}):
# Check if the Fibonacci number is already computed
if n in memo:
return memo[n]
# Base cases: the first two Fibonacci numbers
if n == 0:
return 0
elif n == 1:
return 1
# Compute the Fibonacci number, store it in the memo dictionary
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]

# Example usage: Find the 20th Fibonacci number
print(fibonacci(20))


Output

6765

In this example, we use a dictionary called memo to store previously computed Fibonacci numbers. If the function is called with the same value n again, it first checks whether the result is already in the memo dictionary. If it is, the function returns the value from the dictionary instead of recalculating it, saving time and computational resources.

This method is significantly faster than the simple recursive method, as it eliminates the need for repeated calculations by storing results that can be reused. It’s a prime example of how dynamic programming can optimize recursive algorithms to be more practical and efficient for larger inputs.

Nth Power of Matrix Approach to Find and Print Nth Fibonacci Numbers

Another advanced method to efficiently calculate large Fibonacci numbers is by using the Nth power of a matrix approach. This technique leverages matrix multiplication properties to find Fibonacci numbers in logarithmic time, which is much faster than the previous methods for large values of N.

The Fibonacci sequence can be represented using a transformation matrix. When this matrix is raised to the power of N−1, the top right value in the resulting matrix is the Nth Fibonacci number. Here’s a basic breakdown of how this works:

Define the transformation matrix for Fibonacci sequence:

[1 1]
[1 0]


Compute the Nth power of this matrix.

The value at the first row and second column of the resulting matrix is the Nth Fibonacci number.

Here's a Python implementation : 

  • Python

Python

import numpy as np

def matrix_power(matrix, n):
# Base case: return identity matrix if n is 1
if n == 1:
return matrix
elif n % 2 == 0:
half_power = matrix_power(matrix, n // 2)
return np.dot(half_power, half_power)
else:
return np.dot(matrix, matrix_power(matrix, n - 1))

def fibonacci(n):
if n == 0:
return 0
# Transformation matrix for Fibonacci sequence
transformation_matrix = np.array([[1, 1], [1, 0]])
# Raise the matrix to the power of (n-1)
result_matrix = matrix_power(transformation_matrix, n - 1)
return result_matrix[0][1]

# Example usage: Find the 15th Fibonacci number
print(fibonacci(15))

Output

377


This script uses a helper function matrix_power to compute the matrix raised to the power of n−1 using recursive squaring, which is efficient. The fibonacci function then applies this power to the transformation matrix to extract the Fibonacci number.

This matrix power method is highly efficient for very large numbers because it reduces the number of computations dramatically by using matrix properties. It’s an excellent example of how mathematical concepts like matrices can be applied to improve computational algorithms significantly.

Frequently Asked Questions

Why does the simple recursive method for Fibonacci numbers get slow for large inputs?

The simple recursive method calculates the same Fibonacci numbers multiple times, leading to exponential growth in calculations as the input value increases. This redundancy makes it inefficient for large numbers.

How does dynamic programming improve the calculation of Fibonacci numbers?

Dynamic programming improves efficiency by storing previously calculated Fibonacci numbers. This prevents repeated calculations, allowing the function to return results much faster and using fewer resources.

Why use the matrix method to calculate Fibonacci numbers?

The matrix method is efficient for large numbers because it reduces the problem of calculating Fibonacci numbers to matrix exponentiation, which can be done in logarithmic time. This significantly speeds up the process compared to other methods.

Conclusion

In this article, we talked about several methods to calculate Fibonacci numbers, starting with a basic recursive approach and progressing to more sophisticated techniques like dynamic programming and matrix exponentiation. Each method has its advantages and is suited for different scenarios, with the matrix method being particularly effective for large inputs due to its logarithmic complexity. Learning these different approaches not only helps in solving the specific problem of calculating Fibonacci numbers but also enhances our overall problem-solving skills in programming. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Sum of the combination of numbers | Part-2
Next article
Program to Find Factorial of a Large Number Recursively
Live masterclass