Recursion

Recursion      AU : Jan.-18, Dec.-19, Marks 10

Definition : Recursion is a property in which one function calls itself repeatedly in which the values of function parameter get changed on each call.

Properties of Recursion

There are three important laws of recursion –

1. A recursive function must have a base case.

2. A recursive function must change its state and move toward the base case.

3. A recursive function must call itself, recursively.

 

Example 3.7.1 Display the numbers from 10 to 1 (ie, numbers in reverse order) using recursion in python. Also draw the stack diagram representing the execution of the program.

Solution :

def display(n):

if n < = 0:

return

else:

print(n)

display(n-1)

Output

The execution of above program can be diagrammatically shown as follows:

 

Example 3.7.2 Write a python program for recursive factorial function,

Solution :

def factorial(n):

if n = = 0:

return 1

else:

result = n * factorial(n-1)

return result

print(factorial(5))

Output

120

 

Example 3.7.3 Write a python program to display the Fibonacci series upto n numbers using recursion

Note The Fibonacci numbers are 0,1,1,2,3,5,8,13,21,34,.., where each number is a sum of the preceding two numbers.

AU : Jan.-18, Marks 8

Solution :

def fibonacci(n):

if(n < = 1);

return n

else:

return(fibonacci(n-1) + fibonacci(n-2))

print("Enter number of terms ")

n = int(input())

print("Fibonacci sequence is as follows...")

for i in range(n):

print (fibonacci(i))

Output

 

Example 3.7.4 Implement a recursive function in python for sieve of Eratosthenes. The Sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a specified integer.

AU : Dec.-19, Marks 10

Solution :

def Sieve(i,num):

if num = ri:

return 0

else:

if(num%i==0);

return 1

else:

return Sieve(i+1, num)

n = int(input("Enter last Number:"))

print("Prime Number Between 1 to n are: ")

for i in range(2,n+1):

if(Sieve(2,1)= =0):

print(i,end="")

Output

Enter last Number:50

Prime Number Between 1 to n are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

>>> 

 

1. Advantages and Disadvantages

Advantages

1) It reduces the length of code.

2) It is very useful while applying the same pattern of solution.

3) It reduces unnecessary calling of function.

4) Big and complex iterative solutions are easy and simple with Python recursion.

Disadvantages

1) Recursive functions are slower than iterative solutions.

2) It is hard to analyse or understand the code.

3) It may require a lot of memory space to hold intermediate results on the system stack.

4) The computer memory may run out of memory if the recursive calls are not properly checked.

 

2. Comparison of Recursions with Iteration

Recursion

1. The function is called itself repeatedly.

2. The intemal stack is used to store the set of local variables

3. Recursion is always applied to function

4. Slow in execution.

5. Recursion reduces the size of the code.

Iteration

1. The set of instructions is executed repeatedly

2. It does not use stack.

3. Iteration is applied to control statements such as for loops, while and do while statements.

4. Fast in execution.

5. Iteration makes the code lengthy

Review Questions

1. Define recursion with an example.

AU: Dec.-19, Marks 2

2. What is recursive function ? What are its advantages and disadvantages ? Compare it with iterative function.

AU: Dec 19, Marks 6