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
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.
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.
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
- C Program GCD By Recursion
- C Program Sum of One to N by Recursion
- C Program Sum of Digits by Recursion
- C Program Reverse Number by Recursion
- C Program Fibonacci Series by Recursion
- C Program Power By Recursion
- C Program Find Factorial by Recursion
- C Program Quick Sort
- C Program Merge Sort
- Using Recursion in Java Find Factorial of Number
- Recursion in Java Explained With Examples
- Program Factorial by Loop and Recursion Versions