Learning to write recursive functions and think recursively is crucial to any coder or software engineer who wants to create apps, do web development, and/or build their careers overall. In this article, we'll focus on how to write recursive functions using examples, starting with simple examples and progressively moving to more complex examples.
Introduction to the Concept of Recursion
Recursion is a behavior exhibited by a function or object when it is defined in terms of itself, or parts of itself. In the context of a function, it is a function which invokes itself depending upon some criteria. For a complete overview of the basic concepts of recursion using real life examples and visuals, please refer to our non-technical introduction to recursion.
How to Write a Recursive Function
To write a recursive function, you will need to analyze the problem you are trying to solve and answer the following questions:
- What is the base case?
- Your recursive function will need to have a base case where the recursion stops. Otherwise, the program will end up in an infinite loop. What are the base case(s), and how many base cases are there?
- What is the recursive case? In what cases will the function call itself?
- In what cases will the function call itself, and if more than one, how will they differ?
- How will the arguments in the recursive call differ?
- In almost all cases, when the recursive call takes place, the arguments fed into that call will be slightly different than those received by the current function call. For example: a sequence defined recursively might do some operation
f(n) = 5 * f(n-1)
. In that case, the argument differs by -1.
In the examples below, we'll describe each type of algorithm, discuss the base cases and recursive cases, provde any additional required information, then proceed to the code. Try following along with the code and use the test cases to help identify how the code will behave based on different types of input. Note that the algorithms given in these examples are not necessarily the most efficient algorithms for these solutions, but they will serve as good examples for recursion.
Recursion with Factorials
The classic example used when teaching recursion is to calculate a factorial number. A factorial number is written as n!, where n is an integer >= 1, and is calculated by multiplying 1 ⋅ 2 ⋅ ... ⋅ n. One way to implement an algorithm to calculate a factorial value is to do so with a recursive function. In the code below, we'll implement a recursive function calcFactorial which will call upon itself to fully calculate a factorial:
- Base Case: if n = 1, we can immediately return 1.
- Recursive Case: return n multiplied by the factorial of n - 1
Multiplying With Recursion
Multiplication is a simple and well known operation, but for the purposes of this example, we will explicitly define it for integers. Multiplication is a process where, for integers a and b, we take b occurrences of the integer a and sum them up. For example: 4 ⋅ 3 = 4 + 4 + 4 = 12. We will use this concept to write a function which uses recursion to multiply two integers by recursively adding up the sum:
- Base Cases: this example has three cases listed below:
- a or b is 0: return 0
- a is 1: return b
- b is 1: return a
- Recursive Case: take the sum of a + multiply a ⋅ (b-1)
Moving Through a Collatz Squence
A famous unsolved problem in mathematics is whether or not the Collatz Conjecture is true. The Collatz Conjecture states that for any start number n, if we continuously apply the function shown below, we will always eventually end up with the number 1. The function below states: if n is even, divide by two and continue. Otherwise, continue with 3n + 1.
$${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}}\\[4px]3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}$$It is widely believed that the conjecture is correct, and the conjecture has been verified experimentally for all n up to roughly 268. Therefore, for our own purposes, we can write a recursive function and trust that for any input we give it, the sequence will eventually end up at 1. Our function will recursively determine the number of steps, or transformations, we must apply to any given input before it reaches 1.
- Base Case: if the input is 1, return 0 (since we don't need to transform 1 to get to 1).
- Recursive Cases:
- If n is even, call recursively with n/2.
- If odd, call recursively with 3n + 1.
Find the Length of a Linked List
A linked list is a data structure which holds a chain of one or more nodes. Each node has a value associated with it, and possibly a reference to another node. An example linked list with three items is shown below. The last node with an arrow does not have a next node, so it is pointing to an empty reference (which we will treat as null in the code below).
In order to find the length of a linked list, we will need to visit each node, starting with the first node, until we find a node which has no next node after itself, and keep count along the way. We can write this type of functionality using recursion.
- Base Case: the provided node does not have a next node associated with it.
- Recursive Case: the node does have a next node associated with it.