# Recursion

Written by

Recursion is a method of solving problems in computer programming that involves functions which call themselves. This concept might seem a bit odd the first time you hear it, but once you wrap your head around it you will find it a useful tool. It is best suited to solving problems that break down into sub-problems that resemble the initial one.

The classic example used in most textbooks is taking the factorial of a number. We use the exclamation mark to designate the factorial so n! is simply the product of all the integers from 1 up to n. For example, 3! is 1 x 2 x 3 which is equal to 6, 4! is 1 x 2 x 3 x 4 and 5! is 1 x 2 x 3 x 4 x 5 and so on. What makes this function a candidate for a recursive solution is that the factorial of any positive integer is that integer multiplied by the factorial of the preceding integer. That is to say n! = n (n-1)!

This allows us to write a program such as that shown in Figure 1. This is a screenshot of an online C compiler with the code window at the top and the console output below.

We call the factorial function from main, with a parameter of n = 16. The factorial function then calls itself with a parameter of 15, which calls itself with a parameter of 14 and so on until n = 1. In this call the factorial function will return with a value of 1.

Control will return to the version of the factorial function called with a parameter of 2 which will return 1 x 2 to the version called with a parameter of 3. This in turn will return with a value of 1 x 2 x 3 and so on until the initial call to factorial from main with n = 16 returns the final result of 20 922 789 888 000.

It is really important to have the test for n equal to one and a return path from the recursive function that does not call itself. This is called the “base case” and is necessary to prevent the recursion carrying on forever.

We essentially have a series (sixteen in this example) of nested function calls. Each nested call will take up a finite amount of space on the stack to keep track of the return address and any local variables. The risk is that you can run out of stack space if the recursion gets too deep. This can quickly become an issue on microcontrollers with limited RAM, so be careful.

This was a bit of a trivial example since its pretty easy to calculate the factorial for a number without recursion, as in Figure 2. Here we use a simple loop to control the multiplication. This will be comparable in code size and execution speed with the recursive example, and will use less of the stack, so it is probably the way to go. You can almost always use a non-recursive algorithm where you can use a recursive one, its just a matter of which solution is better for your application.

Here is another common use case for recursion which is a bit less trivial. It involves finding the greatest common factor (GCF) of two integers. You could use Euclid’s algorithm which I have written about here before, but here is a neat recursive approach.

Figure 3 shows the code and the result for a couple of large integers. We take advantage of the fact that (assuming ab) the GCF of a and b is b if b divides into a with no remainder, otherwise the GCF must be the GCF of a and the remainder.

This is shown symbolically in Equation 1. You can see that this is a great candidate for recursion since the solution to finding the GCF involves finding the solution to another GCF. There is also a clear base case, when b divides into a with no remainder.

The recursive function (Figure 3) therefore takes two parameters, a and b, and checks for the base case (where b is a factor of a). In this case it returns b. Otherwise, it calls itself with the parameters a and the remainder.

It’s probably easier to understand with a simpler example. Table 1 shows the steps for the integers 28 and 16. Initially the GCF function is called with parameters 28 and 16. The remainder of 28÷16 is 12, so the function calls itself with parameters 28 and 12. This time the remainder of 28÷12 is 4 so the GCF function is called again with parameters 28 and 4.

This time (iteration 3) the remainder of 28÷4 is zero, so the result 4 is returned through the previous iterations to the top level. This is indeed the GCF of 28 and 16.

References
GDB online Debugger. “Online C Compiler – Online Editor.” Accessed October 24, 2023. https://www.onlinegdb.com/online_c_compiler.

“Recursion (Computer Science).” In Wikipedia, August 21, 2023. https://en.wikipedia.org/w/index.php?title=Recursion_(computer_science)&oldid=1171476580.

 Keep up-to-date with our FREE Weekly Newsletter! Don't miss out on upcoming issues of Circuit Cellar. Subscribe to Circuit Cellar Magazine Note: We’ve made the Dec 2022 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine. Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas.