Define the term Recursion? Give a recursive algorithm to find nth term of a Fibonacci series?
Q.) Define the term Recursion? Give a recursive algorithm to find nth term of a Fibonacci series?
Subject: Data Structure and AlgorithmRecursion is a method of solving problems in computer science where the solution to a problem depends on solutions to smaller instances of the same problem. In programming, recursion is a process in which a function calls itself as a subroutine. This allows the function to be written in a much simpler form, and it can also manage tasks that would be complex, or even impossible, with other methods.
The basic idea behind recursion is that a problem is divided into smaller and simpler sub-problems until we reach a stage where the problem can be solved easily. The solution of all sub-problems is then combined to give the solution of the original problem.
Here is a simple recursive function to illustrate the concept:
def recursive_function(n):
if n == 1:
return 1
else:
return n * recursive_function(n-1)
In the above function, recursive_function
is a recursive function as it calls itself.
Now, let's discuss the Fibonacci series and how to find the nth term of a Fibonacci series using a recursive algorithm.
The Fibonacci series is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. That is, the sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so forth.
The mathematical equation describing it is:
F(n) = F(n-1) + F(n-2)
With seed values :
F(0) = 0, F(1) = 1
Here is a simple recursive algorithm to find the nth term of a Fibonacci series:
def fibonacci(n):
if n <= 0:
return "Input should be positive integer"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
In the above function, fibonacci
is a recursive function. It calls itself with arguments n-1
and n-2
until it reaches the base case (n == 1 or n == 2).
For example, if we want to find the 6th term of the Fibonacci series, we can call the function as follows:
print(fibonacci(6)) # Output: 5
This means that the 6th term of the Fibonacci series is 5.