Recursion

Published Apr 23, 2022
Contribute to Docs

Functions in Python can call themselves — a concept known as “recursion”. Recursion is a technique that allows a function to be broken down and operated on more efficiently.

Syntax

def recursiveSyntax(parameter_1, parameter_2, ..., parameterN):
  if(base_cases involving parameters):
    return "this data"
  else:
    recursive_call = recursiveSyntax(parameter_1 - 1, parameter_2 - 2, parameterN)
    return recursive_call

Recursive functions are commonly structured to operate on their parameters under two scenarios:

  • A recursive_call to the recursiveSyntax() but with smaller values for the parameters.
  • One or more base_cases that stop the line of recursive calls and return data that can be aggregated back up the recursive_call chain.

Example

In the example below, a recursive call to sodaCount is made until the count reaches zero, printing a message each time:

def sodaCount(count):
if(count==0):
print("All of the soda is gone!")
return
else:
print(f"{count} bottles of soda left on the shelf.")
return sodaCount(count-1)
print(sodaCount(5))

The resulting output will look like this:

5 bottles of soda left on the shelf.
4 bottles of soda left on the shelf.
3 bottles of soda left on the shelf.
2 bottles of soda left on the shelf.
1 bottles of soda left on the shelf.
All of the soda is gone!
None

Codebyte Example

Consider the Fibonacci sequence, whose first two terms are explicitly defined to be 0 and 1. Each subsequent term is constructed by taking the sum of the previous two terms. Thus, the first six terms of the sequence are 0, 1, 1, 2, 3, and 5.

Defining a function that prints the n-th Fibonacci number is most easily achieved using recursion.

us
Visit us
code
Hide code
Code
Output
Hide output
Hide output
Loading...

Inside the else block of the function definition, two recursive calls to fibonacci() (representing the two previous numbers) are added and returned. Once n is equal to 0 or 1, the base case (the if block) runs instead.

All contributors

Looking to contribute?

Learn Python on Codecademy