A collection of recursive algorithm techniques in C that can be applied to real-world applications

Introduction


Hello avid blog readers! After months of enjoying the summer and basking in the warm weather, I am finally back with an entry for the month of September. Today I am going to look at something that is a little more on the technical side and something that mostly only software developers would care about. If you aren't interested in the inner workings of recursive algorithms and how one can implement them in C, feel free to skip this entry. I will be back with another one for the month of October, that might be more accustomed to the usual entries and topics that I am discussing in this blog. Let's begin and start with the basics

(Note: This blog entry assumes you have never taken a Computing I or II course before in college and have no prior knowledge writing algorithms in C. It DOES ASSUME you are familiar with the C programming language though)

What is recursion?


Recursion according to a simple definition in [1] is a circular definition. When something is defined "recursively" it is defined in terms of itself. In other words, it could be a number that calls itself repeatedly over and over again. By decomposing a a larger problem into a subproblem using stepwise refinement we are defining a recursive solution. Several algorithms and examples will make this clearer:

Say we wanted to write a function in C that computes the sum of ANY two squares? This is very common problem for Computing I students. Mathematically it would look like this:

SumSquares(2,4) = 2^2 + 2^3 + 2^4 = 4 + 8 + 16 = 28. This seems like pretty simple counting problem in mathematics? right?

When students have to implement it algorithmically in C this is where they get tripped up! Below is an example of an function in C that can square the sums.

int SqrSum(int x, int y) // function prototype excepts any two 'ints' as input! {

int counter, sum; // declare counter and sum output
sum = 0; // initialize the sum. Set it equal to zero

for (counter = x; counter <= y; y++) {
sum = sum + y*y; // iterate through each value summing the output. Could also be written as sum += y*y shorthand.
}
return sum; // return SumSquares as a type 'int'.
}


In practice, this is collectively referred to as iterative algorithm or "solution". We iterate through each individual number, until solution presents itself. Elogant right? Well as turns out there are three other ways to implement recursive algorithms. One is the "common" approach (This is the most common way we see recursion implemented on the net). The other way is called the going-down approach and finally there is the divide and conquer approach. This an approach where the problem is divided into two halves and solved. Before this entry is over, we are going to look at all three!

Popular recursion


Popular recursion is more common place on the Internet, if you do a search for 'recursive algorithms'. It constitutes most primitive recursive functions, like popular Ackermann function that requires more mass then what is in the "known" Universe to compute! (I am not making that up either ;-) ). Let's look an example of function in C, that can perform common recursion:

int SqrSum(int x, int y) // function prototype excepts any two 'ints' as inputs as long as x <= y
if (x < y) {
return x*x + SqrSum(x+1, y); // call the 'base case' SqrSum() function prototype again going up and return it!
else {
return y*y; // return the 'top halve' by multiplying it with itself, if x < y
}
}


This is the MOST straightforward way to perform recursion and one that you will see used a number of times in a number of different algorithms in C.

Going-down recursion


Now, let's take a look at the less popular going-down approach. Here we are using stepwise refinement AGAIN to decompose the problem into smaller subproblems. Let's look at an example function in C that can perform this type of recursion:

int SqrSum(int x, int y) // function prototype excepts any two 'ints' as inputs as long as x <= y
if (x < y) {
return x*x + SqrSum(x, y-1) + y*y; // call the SqrSum() function prototype again going top down and return it!
else {
return y*y // return the 'top halve' by multiplying it with itself, if x < y
}


As you can see above, this is the less common approach to solving a problem recursively. It's called "Going-down", because we start at the top and work our way down! The inverse of the most common method used above.

Divide and Conquer recursion


Divide and conquer is a technique that is taught in most Computing I and II courses. It's very RARE to see if used in recursive algorithms and is the most complicated. One MIGHT consider this approach, if they are looking to analyze the run time or the execution speed of the actual algorithm itself and need to run in "optimal" time (We will save that for a more complicated Analysis of Algorithms course though. It's beyond the scope of this writing and requires more math then one can fathom). Let's look at an example function in C that perform this type of recursion:

int SqrSum(int x, int y) // function prototype excepts any two 'ints' as input as long as x <= y
int midpoint; // declare the midpoint of a finite set of 'ints'
if (x == y) {
return x*x // return the 'base case' by multiplying it with itself, if the two are equal!
} else {
midpoint = (x+y)/2; // find the midpoint or both finite sets and cut them into halves!
return SqrSum(x, midpoint) + SqrSum(midpoint+1, y); // return the first half and the second half recursively and combine them into one!
}
}


As you can see this is more of solution for a course that, would require "optimal" running time (depending the number of integers in a finite set). It's the LEAST common solution and one you won't find at lot on the net. It's more appropriate for an "Analysis of Algorithms" course, but is presented here for completeness sake. That completes this weeks entry! pheww and you thought this entry would never end! The last thing we are going to look at today is where recursion is actually used in real-world C applications! Here are some places it's used (for those of you who believe that it lives in the confines of "acadamia" or was just used in some course you took way back when, because you had to know it for the exam! ha!).

Real-world recursive instances in C


  • Operating Systems - Here it's used in directory tree traversals 
  • Network Infrastructures - Here it's used in forking network sockets e.g (multi-threaded servers)
  • Embedded devices - Here it's used to to list O.S processes e.g (process trees) 

I hope this entry has been of some use to the individuals who have decided to read it from start to to finish! If you have any other questions leave me comments or get into contact with me! If you want me to make any corrections that you see or additions, please let me know also. I look forward to hearing from you either way. For those of you who were turned off by this jargony entry, I will be back next month with a topic that's music related! Take care and enjoy the start off the fall everyone. Later! ;-D

Reference:


1. Standish, Thomas A. "Introduction to Recursion." Data Structures, Algorithms & Software Principles in C. Addison-Wesley, 1995. pg. 64-69. Print.

Comments

Popular posts from this blog

Encoding Opus files in Linux with opusenc for your own collection and HTML 5

Encoding Vorbis files in Linux using oggenc for your own music collection and HTML 5

Transcoding H.264 files to Google's WebM format (VP8/Vorbis) in FFMPEG 0.6 or better using Linux for your own collection and HTML 5