In this tutorial, we will be examining** recursion** and **recursive functions**.

Recursion is simply when a function calls itself, and recursive functions have a wide range of applications from **solving puzzles to procedural generation**.

Let’s learn about recursion!

Table of contents

### Overview

In mathematics, a “**Recursive Sequence**” is a sequence that refers back to itself. **In computer science, recursion is a function that calls itself**. It is a fairly simple concept. However, as you can imagine, this does present the danger of an **infinite loop**. Thus, a condition needs to be supplied that would end the loop (even though, in the strictest sense, recursion is not a loop). This condition is called the “base” condition. **Recursion is best for problems involving a small number of recursive steps**. Recursion starts to become inefficient when a function must be called many times over.

### Coding Examples

A recursive function can call itself either directly or indirectly. An example in Python of a function calling itself directly would be like this:

def directRecursion(number): if number < 1: return else: number -= 1 print (number) directRecursion(number) directRecursion(12

The function **calls itself within itself**. Notice also that the base condition is whether or not the number is less than one. If it is, then the function returns.

An example of indirectly would be something like this:

def indirectRecursion1(number): if number < 1: return else: indirectRecursion2(number) def indirectRecursion2(number): number -= 1 print (number) indirectRecursion1(number) indirectRecursion(12)

The function **doesn’t directly call itself** but recursion is ultimately achieved.

The above examples will print out a set of **decrementing numbers** like this:

11 10 9 8 7 6 5 4 3 2 1 0

We can also use recursion for mathematical functions like **factorials**. In mathematics, **a factorial of an integer is where the previous integers down to 1 are multiplied together**. Writing a factorial function in Python using recursion looks like this:

def factorial (n): if n == 1: return 1 else: return (n * factorial (n -1)) print(factorial(12))

A **recursive approach to the factorial is ideal for mathematicians** because the syntax of the code is very similar to the notation in mathematics.

In addition to counting problems, recursion has been used to **solve puzzles**. The ancient problem of the **Towers of Hanoi** has a solution that involves recursion. Recursion can be used for solving puzzles like **Sudoku**. The pseudocode for that sort of algorithm might look something like this:

function solveSudoku ( currentBox ) if all the boxes are filled return true; //The puzzle is solved! end if the current box is filled return the result of: solve_sudoku( next box ); //Find the nearest unsolved box end for each possible number from 1 to 9 if that number is valid put that number in the box if solveSudoku is true return true; // success! end end end return false; // failure end

In addition to being used for solving puzzles, **recursion can also be used for visualization**. An example of this would be the “Recursion Tree” created in Logo. Nevertheless, a recursive algorithm can be useful in many instances. Though recursive calls need to be implemented correctly, a recursive solution can quickly tackle a variety of situations that would otherwise be tedious to program (thus reducing time complexity).

All in all, though, creating full recursive algorithms come with many benefits and can give you new ways to deal with certain programming problems.

### More Resources

Wikipedia goes into more detail:

Tutorials that have more coding examples:

- Recursion – University of Utah
- Python Function Recursion – W3Schools
- Python Recursive Functions – PythonTutorial
- Java Recursion – W3Schools
- Mastering Recursive Programming – IBM
- Procedural Maze Creation in C# – Coding Degree

Videos that cover recursion:

- What is recursion? – Computerphile
- Python: RECURSION Explained – Joe James
- Recursion and Dictionaries -MIT Open Courseware
- Algorithms: Recursion – HackerRank

##### BUILD GAMES

**FINAL DAYS: **Unlock 250+ coding courses, guided learning paths, help from expert mentors, and more.