How to write recursive functions

Recursion is a powerful concept in programming, and it can make code easy to read and understand. This tutorial takes a non-recursive function and re-writes it as a recursive function. These are written in C#, but are compatible with C++ and C. The only difference is that you would use cout << number for C++ and printf("%i", number); for C to write to the console, instead of Console.WriteLine(number).

Common functions take an input (or no input), go through a set of steps and optionally return an output. Functions look like this:

outputType functionName(input) {
    commands
}

So, for example, if we want to add two numbers and return the result, we tell it the output is an “int” (integer) type, name the function “add”, and tell it to accept two inputs, x and y:

int add(int x, int y) {
    return x + y;
}

Below is a function to count to 9 starting from a number number.

void countTo9(int number) {
    while (number <= 9) {
        Console.WriteLine(number);
        number = number + 1;
    }
}

number has to be an integer, because I don’t want to count to 9 with decimals, so I explicitly restrict it from using decimals by declaring it as an “int”. I then tell the CPU to count up to 9, one number at a time, and log it to the console. The word before the function name is where you normally tell the program what the variable type of your output is. In this case, it doesn’t return any type of variable, so it is “void”. All it does is run what is inside the function without having any output. The value of number is the start number at the beginning, but we increment it during the process, so over the course of the function, it has changed its value from what was inputted and worked its way up to 9. Changing of a variable’s value is called “mutation”.

The “while” statement is a looping construct that lets you specify what to compare the variable against, to determine if the loop runs again. A while loop evaluates the comparison before it runs the code inside the block.

When the main program calls this function, a new space in memory is allocated for the variable number and filled in by copying a value from another memory cell. Afterward, this value is mutated.

The Recursive Way

void countTo9(int number) {
    if (number == 9) {
        return number;
    } else {
        Console.WriteLine( number );
        return countTo9(number + 1);
    }
}

So let’s say we want to count from 6 to 9. We call countTo9(6). To save space, I have renamed “countTo9()” to “f()” below.

f(6) outputs "6" and calls f(6+1) which is f(7)
f(7) outputs "7" and calls f(7+1) which is f(8)
f(8) outputs "8" and calls f(8+1) which is f(9)
f(9) outputs "9" and exits the function.

The essence of recursion is that the output of the current run of your function becomes the input for the next run. Another way to look at it is that the current run depends on the previous run.

Visually, the call chain is:

f(6)
 └ f(7)
   └ f(8)
     └ f(9)

We know that getting from 6 to 9 requires getting from 7 to 9, so we just call the same function to get from 7 to 9. Getting from 7 to 9 requires getting from 8 to 9, so we just call a function to get from 8 to 9. Getting from 8 to 9 requires getting from 9 to 9, so we just call a function to get from 9 to 9. Getting from 9 to 9 requires nothing, so we stop. When the input is the same as the stopping value, this is called the “base case”.

To summarize the above paragraph: for a function, f(x), the n’th execution of f(x) has the (n-1)’th execution of f(x) as its input. We can express this in a recursion statement:

f(x_n) = f(x_n-1) + 1

Notice that, since we were adding 1 every time, we have + 1 at the end.

Most people have seen and used recursion before without even realizing it. Look back at the non-recursive function and notice that the recursion expression above looks similar to our incrementer statement, number = number + 1. It takes a variable, adds 1 to it, and then stores the output back into the variable, to be re-used in the future. The new value of number is a function of the current value of number, which is a function of the previous value of number, and so on. Recursive functions use this same idea, but express it directly. Using a recursive function removes the need for a programmer to remember the state of their variables during runtime, which can be intuitive or unintuitive, depending on how you conceptualize the problem. However, the best part is that this proves to be very useful for writing code that doesn’t cause program crashes or unstable systems, as it can avoid the need to keep track of memory allocation. This strategy is also the basis of functional programming. Enforcing this pattern allows the programmer to tackle the problems of state and function separately, removing alot of the headache of debugging.