How to Use Recursion – Programming Tutorial

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:

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.