Define the term Recursion? Give a recursive algorithm to find n^th term of a Fibonacci series?

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually, recursion involves a function calling itself. In programming, recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc.

For example, we compute factorial n if we know factorial of (n-1). The base case for the recursion are n = 0 where the answer is 1. We use the following relation to express this.

factorial(n) = n * factorial(n-1) for n > 0
factorial(n) = 1 for n = 0

Now, let's discuss the Fibonacci series. The Fibonacci sequence 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, ....

The mathematical equation that defines Fibonacci sequence is

F(n) = F(n-1) + F(n-2)

with initial conditions

F(0) = 0, F(1) = 1

Here is a simple recursive algorithm to find the n^th term of a Fibonacci series:

def fibonacci(n):
    if n < 0:
        print("Incorrect input")
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

In this algorithm, the base case is when n is 0 or 1. If n is either 0 or 1, the function returns n. If n is greater than 1, the function calls itself with the arguments n-1 and n-2, and returns their sum. This is a direct translation of the mathematical definition of the Fibonacci sequence.

However, this algorithm is not efficient because it does a lot of repeated work. Each time we call the fibonacci function with a certain argument, it will call itself twice with smaller arguments, and each of those calls will again call fibonacci twice, and so on. This leads to an exponential number of function calls, even for small inputs.

A more efficient approach would be to use dynamic programming, where we store the results of the subproblems so that we can reuse them later instead of recomputing them.