Recursion in C: A Brief Guide

The problem with recursion in C is that there are a lack of simple yet illustrative demonstrations of how it may work. Being an imperative programming language which deals in changes of state, recursive techniques are not as important in C as they are in some programming languages, such as the Scheme dialect of Lisp. As well as that, two of the traditional mathematic expressions used to illustrate recursion, calculating a factorial and calculating Fibonacci numbers, are both inefficient uses of recursion in a computer. However, for the sake of completeness, I’ll illustrate both of them and explain afterwards why they are inappropriate examples for recursion.

So, what is recursion? Simply, it could be described as a method where the solution of a problem depends on solutions to smaller instances of the same problem. This might manifest itself as a function calling itself with a smaller set of arguments, or a lower value for an argument, for instance. Any function in C may call itself, creating a new instance of the function with new arguments.

We can show this easily by taking a function which calculates the factorial of a number. A factorial is calculated by taking a base integer, and multiplying it by all integers lower in value than it down to 1.

For example:

1! = 1
3! = 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
0! = 1 /* Special case scenario */

Because of the relationship between higher and lower factorials, the procedure of calculating a factorial can be described recursively, or in relation to the process of calculating a factorial itself:

8! = 8 * 7!
8! = 8 * 7 * 6!
8! = 8 * 7 * 6 * 5!
...

This can be illustrated in a C function as such:

unsigned int fact (unsigned int n)
{
  if (n < 2)
     	return 1;
  else
	return n * fact(n - 1);
}

The first calling of the function from outside the function itself initialises it with an unsigned integer value, which is checked. If the value for n is less than 2, the function ends very simply by returning 1. Otherwise, the return value multiplies n with whatever the result of calling the fact() function with a new value equal to (n – 1) is.

Let’s say we called fact() in main with the value 5:

fact(5) = 5 * fact(4)
fact(5) = 5 * 4 * fact(3)
fact(5) = 5 * 4 * 3 * fact(2)
fact(5) = 5 * 4 * 3 * 2 * fact(1)

At this point, fact(1) is called. The if statement in the function is now satisfied, and so this calling of the function returns the value 1.

fact(5) = 5 * 4 * 3 * 2 * 1
fact(5) = 5 * 4 * 3 * 2
fact(5) = 5 * 4 * 6
fact(5) = 5 * 24
fact(5) = 120

Note, however, the pyramidal shape of the arguments in this function. A new instance of the fact() function must be called each time that the value of n is greater or equal to 2, which requires additional memory. Using C’s loop structure, it is possible to calculate a factorial in a single function using an iterative strategy which has better memory efficiency, particularly for higher values of n. This is illustrated below:

unsigned int fact_iter(unsigned int n)
{
	int product = 1;
	for (n; n > 1; n--)
	    product *= n;
	return product;
}

A similar number of calculations takes place in the iterative strategy as in the recursive strategy, giving both functions O(n) time complexity (i.e. the time taken to finish the calculation is proportional to the value of n), but as only a single function is needed in the iterative strategy, the space complexity of the iterative strategy is superior to that of the recursive strategy. The amount of space required for the iterative strategy is constant for any value of n (i.e. O(1)); the amount of space required for the recursive strategy is proportional to the value of n (i.e. O(n)).

Another mathematical function which demonstrates a recursive nature is the calculation of the Fibonacci numbers. The Fibonacci numbers are interesting to mathematicians because of their close relationship to the Golden Ratio. Each Fibonacci number is the sum of the previous two, which leads to a list like so:

1 1 2 3 5 8 13 21 34 55...

This relationship can be described recursively as so:

fib(n) = fib(n - 1) + fib(n - 2)

In C, this would be written in this way:

unsigned int fib(unsigned int n)
{
	if (n < 3)
	   return 1; /* fib(1) == 1; fib(2) == 1 */
	else
	   return fib(n - 1) + fib(n - 2);
}

Unfortunately, this use of recursion is even less suitable than that used in the calculation of a factorial. The function calls itself twice every time that the value of n passed to it is greater than or equal to 3; for fib(20), this results in fib() being called over 13,000 times! This function therefore has a time complexity of O(fib(n)), demonstrating a completely absurd use of recursion when an iterative strategy like this:

unsigned int fib_iter(unsigned int n)
{
	int sum = 2;
	int minus_one = 1;
	int minus_two = 1;

	if (n < 3) {
            return 1;
        } else { 	/* Take away 3 from x and keep going while n > 1 */
	   for (n -= 3; n; n--) {
	       minus_two = minus_one; /* minus_two equals the old minus_one */
	       minus_one = answer; /* minus_one equals the old answer */
	       answer = minus_two + minus_one;
	   }
	}

	return sum;
}

has time complexity O(n), and therefore runs far quicker on any non-trivial case.

So far, we have two functions which demonstrate mathematical examples of recursion where it is not suitable to use that recursive nature to calculate them in a computer. At this point, you may be asking, “Is there any point to recursion?”

The answer is: “yes, but not with anything that’s particularly easy to explain.” There is, however, a very strong argument for having recursion in the C language, and one of the examples given in The C Programming Language (Brian Kernighan and Dennis Ritchie, 2nd Edition, 1988) proves why.

The quicksort, invented by C. A. R. Hoare in the 1960s when on an academic trip to Russia, is a comparison sort which, as the name suggests, is one of the quickest sorting algorithms that has ever been invented. It uses a “divide and conquer” strategy, where a single element is chosen as a “pivot value” and the rest of the values are partitioned into two subsets: Those values which are less than the pivot value, and those with a greater value. The same process is then done recursively to the two subsets, and the recursion continues until there is only one element in a subset, whereby nothing needs to be done.

The following code comes from the fourth chapter of The C Programming Language, and demonstrates a version of the quicksort algorithm suitable for sorting integer arrays. A version of this that is suitable for any sort of element is available in the C standard library, under the function name qsort() defined in <stdlib.h>.

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
	int i, last;
	void swap(int v[], int i, int j);
	if (left >= right) /* do nothing if array contains */
	   return;	/* fewer than two elements */
	swap(v, left, (left + right)/2); /* move partition elem */
	last = left;
	/* to v[0] */
	for (i = left + 1; i <= right; i++) /* partition */
	    if (v[i] < v[left])
	       swap(v, ++last, i);
	swap(v, left, last);  /* restore partition elem */
	qsort(v, left, last-1);
	qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
	int temp;
	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}

In this function, an integer array is passed to the function, along with the leftmost and rightmost bounds of the element that are to be sorted. A function, swap(), is defined, which has an integer array and two integer values corresponding to array elements as arguments. The operation of the swap() function is similar to the swapping operations done in the bubble sort and shaker sort algorithms.

From here, if the element to be sorted only has a single element, which is defined by the value of left being the same as the value of right, the function returns to the calling function. There is nothing to be done; the sub-array of one element is already sorted by default. Otherwise, the partitioning element, which is the middle element of the array in this partitioning strategy, is swapped with the first element. The position of the left element is stored in a separate integer variable named last, so that it may be restored later.

The partitioning then begins. For all values of the array subset apart from left, if the value of v[i] is less than v[left], the element v[i] is moved to the left-hand side of the array subset. This continues until all values have been divided into values smaller than v[left] and values larger than v[left]. The qsort() function is then called again twice, once for each subset that has been created.

Quicksort may be a lot more difficult to understand than the likes of bubble sorting because of the extra complexity, but in this circumstance, the extra complexity in the function, along with its recursive nature, makes this a quicker option than an iterative strategy like bubble sorting, selection sorting or even the relatively efficient Shell sort. With a time complexity of O(n log n) in the average case, it blows the likes of bubble sorting and selection sorting out of the water in most cases, while only the likes of merge sort and heapsort can really complete with the quicksort algorithm for speed in most cases.

Advertisements

One Response

  1. If you are going for finest contents like me, only pay a visit this website everyday for the reason that it offers quality contents, thanks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: