Security-Oriented C Tutorial 0x16 - Functions Part IV: Recursion

Hello again, and welcome back to another tutorial on functions, this time, covering recursion.

What Is Recursion?

Recursion is the calling of a function within itself so that it repeats the process, kind of like a loop. Recursive functions are used in situations where a problem can be broken down into smaller, simpler problems of itself. Let's see an example.

Calculating Factorials

For those who do not know what a factorial is, it's a mathematical operation (represented by the ! symbol) which is applied to a single positive integer. It applies a multiplication of itself and and all of the integers before it up to and including 1, i.e. n! = n * n-1 * n-2 * ... * 1. An example, 4! = 4 * 3 * 2 * 1 = 24.

Okay, enough mathematics, it's wasting my precious brain cells. How would we create a program to solve factorials?

Example Code

A recursive function must fulfill two requirements:

• The base case
• The recursive case

The base case is a situation where the recursion hits its limit and stops like the condition of a loop. The recursive case is where the function calls on itself to repeat the process on a smaller version. In our code, we have the base case of n == 0 and a recursive case of return n * factorial (n-1). Here's a visualization if it's a bit confusing.

Compiling and Running

Output is as expected. If we try larger values, the factorial function might give incorrect values because an int is not large enough to hold them. Changing the return type to a double, we can probably have it calculate up to the factorial of approximately 150.

Recursion vs Loops

You may have noticed that its possible to do this with an iterative loop and in actuality, it is probably much better than using recursion in this scenario. If our num starts getting larger, it will take longer and longer for it to finish. If our recursion becomes too large, our stack frame could take up too much memory and possibly even crash the program. Recursion creates a bit overhead, meaning the function requires resources (memory, time, etc.) to operate.

So why use recursion? Recursion should be used when it can provide a simpler solution. Usually, if performance is an issue, a time complexity analysis should be done with both methods where possible, else if complexity is an issue, recursion may usually be preferred. If you compare an iterative solution to the recursive solution...

[Slides from The Computer Science and Engineering faculty of the University of New South Wales]

... the recursive method looks (to me, at least) much simpler. There are naturally recursive situations such as the factorial, list/tree traversals and search techniques (divide and conquer, binary, depth-/breadth-first search, etc) where iterative solutions may not suffice.

Conclusion

Recursion and loops both have their advantages and it really depends on the situation in which we are presented whether to choose one over the other. Unfortunately, I will not be covering algorithms in this course so we may not see recursion much but the more you know!

dtm.