CC Blog Quick Bits Resources

Recursion

Written by Andrew Levido

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.

Figure 1
This listing shows the simple code for calculating the factorial of a number using a recursive algorithm. The factorial function calls itself to calculate the factorial since the factorial of any number n is n (n – 1)!

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.

Figure 2
The factorial function can be implemented just as easily using a non-recursive algorithm as shown here. There are however plenty of problems for which a recursive solution is the most effective.

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.

Figure 3
This algorithm calculates the greatest common factor (GCF) of two integers using a recursive technique. You can see that the recursive approach provides a very simple solution to what can be a difficult problem.

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.

Equation 1

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.


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.

Sponsor this Article
+ posts

Andrew Levido (andrew.levido@gmail.com) earned a bachelor’s degree in Electrical Engineering in Sydney, Australia, in 1986. He worked for several years in R&D for power electronics and telecommunication companies before moving into management roles. Andrew has maintained a hands-on interest in electronics, particularly embedded systems, power electronics, and control theory in his free time. Over the years he has written a number of articles for various electronics publications and occasionally provides consulting services as time allows.

Supporting Companies

Upcoming Events


Copyright © KCK Media Corp.
All Rights Reserved

Copyright © 2024 KCK Media Corp.

Recursion

by Andrew Levido time to read: 4 min