Recursion Explained
Introduction to recursive functions
A recursive function is a function that calls itself until it doesn’t.
The following fn()
function is a recursive function because it has a call to itself:
In the fn()
function, the #...
means other code.
Also, a recursive function needs to have a condition to stop calling itself. So you need to add an if statement like this:
Typically, you use a recursive function to divide a big problem that’s difficult to solve into smaller problems that are easier-to-solve.
In programming, you’ll often find the recursive functions used in data structures and algorithms like trees, graphs, and binary searches.
Python recursive function examples
Let’s take some examples of using the Python recursive functions.
1) A simple recursive function example in Python
Suppose you need to develop a countdown function that counts down from a specified number to zero.
For example, if you call the function that counts down from 3, it’ll show the following output:
The following defines the count_down()
function:
If you call the count_down()
function now:
…it’ll shows only the number 3.
To show the number 3, 2 and 1, you need to:
First, call the
count_down(3)
to show the number 3.Second, call the
count_down(2)
to show the number 2.Finally, call the
count_down(1)
to show the number 1.
In order to do so, inside the count_down()
function, you’ll need to define a logic to call the function count_down()
with argument 2, and 1.
To do it, you need to make the count_down()
function recursive.
The following defines a recursive count_down()
function and calls it by passing the number 3:
If you execute the program, you’ll see the following error:
The reason is that the count_down()
calls itself indefinitely until the system stops it.
Since you need to stop counting down the number reaches zero. To do so, you add a condition like this:
Output:
In this example, the count_down()
function only calls itself when the next number is greater than zero. In other words, if the next number is zero, it stops calling itself.
2) Using a recursive function to calculate the sum of a sequence
Suppose that you need to calculate a sum of a sequence e.g., from 1 to 100. A simple way to do this is to use a for loop with the range() function:
Output:
To apply the recursion technique, you can calculate the sum of the sequence from 1 to n as follows:
sum(n) = n + sum(n-1)
sum(n-1) = n-1 + sum(n-2)
…
sum(0) = 0
The sum()
function keeps calling itself as long as its argument is greater than zero.
The following defines the recursive version of the sum()
function:
As you can see, the recursive function is much shorter and more readable.
If you use the ternary operator, the sum()
will be even more concise:
Summary
A recursive function is a function that calls itself until it doesn’t.
And a recursive function always has a condition that stops calling itself.
Last updated