Examples of Recursion in Python

You can use recursion in Python to solve many different problems. In this article, we are going to share with you a few Python recursion examples for you to learn how to use recursion in Python.

To use recursion, we need to define a base case for our recursive function and define the recursive step where we will call the recursive function again.

Recursion is useful if you need to loop until a certain condition, but don’t know how many steps it might take to get to that condition.

Below are a few examples of recursion in Python.

Using Recursion to Calculate Factorial of Number in Python

The first example of recursion in Python is to find the factorial of a number using recursion.

Finding the factorial of a number using recursion is easy. For all of these examples, we need to define the base case, and then define the recursive step.

The base case for the factorial function is when n is 0 or 1. In that case, we want to return 1. If n is greater than 1, then we will call the function again with n – 1 as the input.

Below is a recursive function for calculating the factorial of a number. I’ve also included some input validation to make sure that the input is a nonnegative integer.

def factorial_with_recursion(n):
    if isinstance(n,int) and n >= 0: 
        if n == 0 or n == 1: 
            return 1
        else:
            return n * factorial_with_recursion(n-1)
    else: 
        return "Not valid input"

print(factorial_with_recursion(3))
print(factorial_with_recursion(5))
print(factorial_with_recursion(8))
print(factorial_with_recursion(12))

#Output:
6
120
40320
479001600

Checking if Word is Palimdrome Using Recursion in Python

Our second example of recursion in Python is checking if a word is a palindrome using recursion.

A palindrome is a word which is the same spelled forward and backward.

For recursion, we need to define a base case and a recursive step.

The base case for our recursive palindrome function is if our word has less than two letters. By definition, a word which is 0 or 1 letters is a palindrome.

The recursive step for our recursive palindrome function is to check if the first letter and last letter are equal. If they are equal, then we should remove the first and last character and check the resulting string.

In the case the first and last characters are not equal, then we should return False since the given word is not a palindrome.

Below is a function which will check if a word is a palindrome using recursion in Python.

def checkPalindrome(word):
    if len(word) < 2: 
        return True
    if word[0] != word[-1]: 
        return False
    return checkPalindrome(word[1:-1])

print(checkPalindrome("hello"))
print(checkPalindrome("anna"))

#Output:
False
True

Fibonacci Series in Python with Recursive Function

We can also create the Fibonacci Series with recursion in Python. Recursive functions can be simple and powerful for dynamically creating or obtaining the desired result.

We can define a recursive function which will get the nth Fibonacci number.

The base case for our recursive function is when we get the first, second or third fibonacci number. These are 0, 1 and 1.

The recursive step calls our recursive function to get the previous Fibonacci number and the Fibonacci number before that and adds them together.

Below are some examples of how to recursively find Fibonacci numbers in Python.

def fibonacci(n):
    if n == 0:
       return 0
    elif n == 1 or n == 2:
       return 1
    else:
       return fibonacci(n - 1) + fibonacci(n - 2)

def fibonacciSequence(n):
    sequence = []
    for i in range(0,n):
        sequence.append(fibonacci(i))
    return sequence

print(fibonacciSequence(10))

#Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Reversing Strings and Lists with Recursion in Python

One last recursion example in Python is using recursion to reverse strings and lists.

The base case for our recursive reverse function is when our string has a length of one. The recursive step keeps slicing the string from the second character to the end and add the first character to the end.

Below are some examples of how to recursively reverse a string in Python.

string = "Hello"

def reverse_string(string):
    if len(string) == 1:
        return string
    return reverse_string(string[1:]) + string[0:1]

print(reverse_string("Hello"))
print(reverse_string("Good Bye"))
print(reverse_string("My name is Billy"))

#Output:
olleH
eyB dooG
ylliB si eman yM

In an almost identical way, we can reverse a list in Python using recursion.

To reverse a list using recursion, the base case for our recursive reverse function is when our list has a length of one. The recursive step keeps slicing the list from the second element to the end and add the first element to the end.

Below is an example of how to use recursion to reverse a list in Python.

lst = [1,2,3,4]

def reverse_list(l):
    if len(l) == 1:
        return l
    return reverse_list(l[1:]) + l[0:1]

print(reverse_list(lst))

#Output:
[4,3,2,1]

Hopefully these Python recursion examples have been useful for you to learn how to use recursion in Python.