What is Recursive Function in Python?

Introduction

Recursive function in Python is the process of defining something in terms of itself. It states that recursion is the programming technique in which a function or an algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.

In programming languages, we know that a function can call other functions, and we can even possibly call the function itself. But in this article, we will focus only on Python language, and in Python language, we can use recursion.

So, to conclude the recursion in Python. It is divided into 2 parts:

• Base Case: The condition to stop the recursion.
• Recursive Case: Part of the function where a function can call itself.

Examples of Recursive Function

• Write a recursive function that will sum all numbers from 1 to n

Explanation:

In the above code, which explains the use of recursion, the code does calculate the sum of n numbers using recursion. If you know the basics of programming, you can easily do the above using a loop, but in this case, let's add one more method to do the same task. As already explained that recursion means calling a function within itself. In this case, the process is going on, calling a function itself several times, until it satisfies the base case condition.

So, the sum function is written as such, suppose when we enter a number 10, it will calculate the 10 + sum(9), and then call the sum function for the value of 9.

which is sum(10) = 1 + 2 + ... + 10 = 55. So, it will return 55 as output.

This is how recursion is working in the above case.

• Write a recursive function that will find the smallest number in a list

Explanation:

This example is a little bit change and tricky because in this case, we are not going to input a number, instead of a number we are passing a list of integers. Before going deep, the task is to calculate the minimum element in the given list. As there are already methods available in Python, here again, we will be using recursion to do our task.

The above example takes an input list of integers and returns the smallest number from the list.

The code will follow this:

Lets us suppose our list is : [3,24,19,90,9,0,-1]

Step 1: Check the size of the list, if 1 then it is the only and the smallest element in the list.

Step 2: If the size is not 1, then check for the 1st and 2nd elements, if the 2nd element is bigger than the 1st element then we can append our smaller element to the list, and pass the list from a greater index, do this process until it reaches our base case, i.e., until there is only 1 element in the array.

Process:

smallest([3, 24, 19, 90, 9, 0, -1, 3]) =

smallest([24, 19, 90, 9, 0, -1, 3]) =

smallest([19, 90, 9, 0, -1, 3, 19]) =

smallest([90, 9, 0, -1, 3, 19]) =

smallest([9, 0, -1, 3, 19]) =

smallest([0, -1, 3, 19]) =

smallest([-1, 3, 19, -1]) =

smallest([3, 19, -1, 3]) =

smallest([19, -1, 3]) =

smallest([-1, 3, -1]) =

smallest([3, -1]) = -1

ANS: -1

• Using recursive functions to find the factorial of an integer

Explanation: In this case, we are going to calculate the factorial of a number using recursion.

Steps that follow recursion.

Lets suppose we want to calculate the factorial of a number 10, then steps will be as follow:

This is somewhat similar to the example to calculate the sum of n numbers.

so, $factorial(10) = 10 * 9 * 8 * ... * 1$

• Using a recursive function to calculate the sum of a sequence

Explanation:

In this example, we are going to calculate the sum of the given sequence of numbers which are given in a array of integers.

Steps that follow recursion are:

For a given sequence of numbers [1, 3, 2, 6, 7, 8, 0], lets calculate the sum.

sumSequence([1, 3, 2, 6, 7, 8, 0]) = 1 + sumSequence([3, 2, 6, 7, 8, 0]) sumSequence([3, 2, 6, 7, 8, 0]) = 3 + sumSequence([2, 6, 7, 8, 0]) sumSequence([2, 6, 7, 8, 0]) = 2 + sumSequence([6, 7, 8, 0]) sumSequence([6, 7, 8, 0]) = 6 + sumSequence([7, 8, 0]) sumSequence([7, 8, 0]) = 7 + sumSequence([8, 0]) sumSequence([8, 0]) = 8 + sumSequence([0]) sumSequence([0]) = 0

Final equation:

Advantages and Disadvantages of Recursion

Advantages:

• Recursion can break a big complex program into simpler small problems.
• It makes our code clean and elegant.
• Sequence generation is easy with recursion rather than using loops.

Disadvantages:

• Recursion calls are sometimes very expensive or insufficient which takes a lot of time and memory.
• Sometimes, creating logic in recursion becomes very difficult and frustrating.
• They are hard for debugging purposes.

Learn More

Recursion in Python