Python Recursion With Example Recursive Function

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

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