# Python Recursive Functions

Summary: in this tutorial, you’ll learn about Python recursive functions and how to use them to simplify your code.

## 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:

`def fn(): # ... fn() # ... `

Code language: Python (python)

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:

`def fn(): # ... if condition: # stop calling itself else: fn() # ... `

Code language: Python (python)

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:

`3 2 1`

Code language: Python (python)

The following defines the `count_down()` function:

`def count_down(start): """ Count down from a number """ print(start)`

Code language: Python (python)

If you call the `count_down()` function now:

`count_down(3)`

Code language: Python (python)

…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:

`def count_down(start): """ Count down from a number """ print(start) count_down(start-1)`

`count_down(3)`

Code language: Python (python)

If you execute the program, you’ll see the following error:

`RecursionError: maximum recursion depth exceeded while calling a Python object`

Code language: Python (python)

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:

`def count_down(start): """ Count down from a number """ print(start) # call the count_down if the next # number is greater than 0 next = start - 1 if next > 0: count_down(next)`

`count_down(3)`

Code language: Python (python)

Output:

`3 2 1`

Code language: Python (python)

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:

`def sum(n): total = 0 for index in range(n+1): total += index return total`

`result = sum(100) print(result)`

Code language: Python (python)

Output:

`5050`

Code language: Python (python)

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:

`def sum(n): if n > 0: return n + sum(n-1) return 0`

`result = sum(100) print(result)`

Code language: Python (python)

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:

`def sum(n): return n + sum(n-1) if n > 0 else 0`

`result = sum(100) print(result) `

Code language: Python (python)

## 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.