Recursion in Python
- Is one of the most powerful tools in a programming language.
- It is defined as defining anything in turns of itself.
- It is used to solved problems involving iteration(multiple education), in reverse order. Iteration loop statements, helps a programmer to carry out certain task a known times or as long as the desired condition is true.
- If a function refers itself, i. e. call itself, it is said to be a recursive function.
- A function contain either a call statement to itself or a call statement to a second function, which again call back, the original function.
- The first type is known as direct recursion and second type is known as indirect recursion.
For a function to be recursive, it must have the following two properties:
- There must be a base criteria for with the function does not call itself.
- Each time a function calls itself, must be closer to the base criteria.
- The function with this two properties is set to be a well define function.
- When a function calls itself recursively, it is known as recursion.
Types of recursion:
- Recursion are of four types.
- Direct Recursion
- Indirect Recursion
- Tail Recursion
- Non-Tail Recursion
Direct Recursion:
- The recursion in which the function calls itself is called direct recursion. In this type, only one function is involved.
Indirect Recursion:
- The recursion in which two function calls each other is known as indirect recursion.
Tail Recursion:
- A Recursive function is called tail recursive if recursive is the last thing done by function,there is no need to keep record of previous state.
Non-Tail Recursion:
- A recursive function is called non-tail recursive if recursive is not the last thing done by function ,there is no need to keep record of previous state.
Advantages of recursion
- Recursion provides logical simplicity to an iterative statement .
- It also provide self documentation of recursive programme.
- It made the code look more simpler and effective.
- Complex function can be further split into various smaller sub-problems .
Drawback’s of Recursion
- A recursive solution to a problem is more expensive than a non-recursive solution.
- Recursive solution takes more time and also occupies greater memory space.
- More space is reallocated.
- Debugging is very difficult.
Implementation of recursion
In general, there are two approaches to writing repetitive algorithms. One is with use of iteration. The other uses recursion.
Recursion:
Suppose P is a procedure containing either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure P. Then, P is called recursive procedure. So, program will not continue to run indefinitely, a recursive procedure must have following two properties:
- There must be certain criteria, called base criteria for which procedure does not call itself.
- Each time the procedure does call itself, it must be closer to base criteria.
- A function is said to be recursively defined if function definition refers to itself. It must have following two properties:
- There must be certain arguments , called base values, for which function does not refer to itself.
- Each time function does refer to itself, the argument of function must be closer to base value.
-
Factorial Function:
Product of positive integers from 1 to n, inclusive is called “ n factorial” and is denoted by n! .
n! =1.2.3… .. .. (n-1) (n-1) n
0! =1, 1! =1, 2! =1.2=2, 3! =1.2.3=6, 4! =1.2.3.4=24
n! =n.(n-1)!
Program
#recursive function
def factorial(k):
if( k==1):
return 1
else:
return k*factorial(k-1)
#user input
num=4
if num<0:
print("enter positive number")
elif num==0:
print("factoial of 0 is 1")
else:
print("factorial of ",num," ",end=" ")
print(factorial(num))
Output:
Factorial of 4 =24
-
Fibonacci sequence
The celebrated Fibonacci sequence is 0,1,1,2,3,5,8,13,24,34,55…….
That is f0=0 and f1=1 and each succeding term is sum of two preceding terms, the next two terms of sequence are:
34+55=89 and 55+89=144
Program
#recursive function
def fib(n):
if (n<=1):
return n
else:
return(fib(n-1)+fib(n-2))
n_terms=9
if n_terms <=0:
print("enter positive value")
else:
print("fib sequence:")
for i in range(n_terms):
print fib(i)
Output:
fib sequence:
0
1
1
2
3
5
8
13
21
| 
| 
