Python Recursion With Example Recursive Function

By | May 4, 2021

Python Recursion With Example Recursive Function – In this Python tutorial we will learn the following important concepts about Recursion in Python Programming Language.

  • What is Recursion?
  • When to use Recursion?
  • Advantages of Recursion
  • Disadvantages of  using Recursion
  • Recursive Function
  • Base Case of Recursion
  • Recursive Case for Recursion
  • Factorial Recursive Function
  • Identifying Base condition and Recursive condition in factorial function
  • Hand tracing a recursive factorial function
  • Complete Source code for Python program to show use of Recursive function Factorial
  • Python Recursion Made Easy
Python Recursion With Example Program

Python Recursion With Example Program

What is Recursion?

Definition: Recursion is a process of calling a function to itself. Actually we can say that

Recursion refers to a situation where a function calls itself again and again until some base condition is not reached.

Recursive Function?

A recursive function is a function that calls itself.

Base Case and Recursive Case

For a recursive function, you only need to define the base case and recursive case, so the code is simpler and shorter than an iterative code.

What is a Base Case or Base Condition in Recursion?

A base condition is a stopping condition to terminate the recursion process. It is a point

when the recursive function will stop to call itself.

Recursive Case or Recursive Condition

It is a condition, when the base case is not reached and the function needs to call itself again.

Python Recursion With Example Program using  Recursive Function

Problem: Write a recursive function to find factorial of a positive number n.
Solution:
We know that factorial of a number n is equal to the product of all numbers from 1 to n.
For example, factorial of 5 = 1 x 2 x 3 x 4 x 5 = 120
we also know that n! = n * (n-1)!
that is 5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
and we know that 1! = 1
Hence by putting the values
2! = 2 * 1! => 2 * 1 =2
3! = 3 * 2! => 3 * 2 =6
4! = 4 * 3! => 4 * 6 =24
5! = 5 * 4! => 5 * 24 =120

Source Code for Python Recursion Example of Factorial

# Write a Python program to find factorial of
# a number using a Recursive function

# define a recursive function
def  factorial(n):
    ''' A recursive function to find factorial of a number'''
    if n==1:
        return 1
    else:
        return n * factorial(n-1)

# get input number from user and pass it to recursive function
n = int(input("Enter a number to find factorial:"))
print("Factorial of ",n," is ", factorial(n))
      

Output of a Sample run – Python Recursion With Example

Enter a number to find factorial:5
Factorial of  5  is  120

What are Advantages of Recursion?

  • Recursion makes code easier to write.
  • It is helpful to reduce code size.
  • Programmers can use recursion to solve the problems which are naturally recursive such as Factorial, Fibonacci series and towers of Hanoi.
  • Recursion adds clarity and reduces the time needed to write and debug code.
  • It is very useful in solving some important data structure problems.

What are drawbacks of using Recursion?

  • Recursive functions are generally difficult to analyze or understand the code.
  • The programs with recursive functions are generally slower especially for large input size n.
  • Recursive functions are generally slower than non-recursive function. That is why they are less efficient in terms of time complexity and space complexity.

 

More Programs on Recursion

Loading

Leave a Reply

Your email address will not be published. Required fields are marked *