Recursion in Python

What is Recursion?
Recursion means defining something by its own meaning. In programming language recursion can be explained as a function calling itself repeatedly.

The best example of using recursion is factorial.
A factorial is calculated by :

n! = n*( n-1)!

The factorial of a number is calculated by multiplying the number with factorial of a number less than itself. So, this process will run until  1! is reached which is equal to 1. This condition is called termination condition. If a termination condition is not specified recursion will run till infinity.
While defining a function using recursion this termination condition is called as base case.

How is recursion achieved?
A recursive definition is made up of two parts .

• Base Case - as specified above its the termination condition else the loop will run till infinty.
• Recursive or Inductive Case - the process of calling the function again with another input

Recursive implementation of Factorial :

    

	def fact(n): if n==1: #Base Case
	return n
	else:
	return n*fact(n-1) #Inductive case

Another famous problem that is solved through recursion is Fibonacci Series which is given by :

fib() = 0,1,1,2,3,5,8,13............

an element at (x+2) position  is calculated in fib by:

fib(x+2) = fib(x+1)+fib(x)

• it has two base case: x=0, or x=1, in general htere can be as many base cases as needed.
• It has two recursive calls as well, again it depends on the need of function

Recursive implementation of Fibonacci Series :

	def fib(x): if x==0 or x==1: #Base Case
	return 1
	else:
	return fib(x-1)+ fib (x-2) #Inductive Case