Simple Recursion in C

Certain objects in mathematics can be defined by the process that creates them, rather than as the end result itself. For instance, pi is defined as the ratio of the circumference of a circle to its diameter. When we think about it, pi is really defined as an algorithm – find out the circumference of a circle, then find out its diameter, then divide the circumference by the diameter. When we have an algorithm that produces a definite result, the algorithm itself can stand in for the result. In C, an algorithm that produces a result is a function, and, after all, we can in C and most C-family languages use a non-void function in place of a value, as long as the return type of the function is compatible with the type of the value we would have otherwise used.

Another example would be a factorial, represented as n!, where n is a positive integer. A factorial is defined as the product of all integers between the specified number and 0. For example, 3! = 3 * 2 * 1, which is equal to 6. While factorials are a pain to compute by hand, computers do them quite nicely, using a trusty loop.

#include <stdio.h>
int factorial(int n);
int main(void){ int num = 3; //3! printf("%d! = %d\n", num, factorial(num)); //increment num num++; //4! printf("%d! = %d\n", num, factorial(num)); printf("Note bene!:\n"); printf("%d! = %d * %d! ", num, num, num-1); printf("= %d\n", num * factorial(num-1)); return 0; }
int factorial(int n){ //use an iterative function for(int i = n - 1; i > 0; i--){ n*=i; } return n; }

 

Our first algorithm for producing a factorial is called an iterative algorithm; it calls for the repetition of a process until a condition is met. But, as we saw above, the factorial for a number is equal to that number multiplied by the factorial of the one less than itself. We can therefore describe a factorial as a chain produced by multiplying each positive number by the positive number before it; of course, this is verbally how we would describe the algorithm, but when it comes to writing it our first instinct is to write, for instance, 3! = 3 * 2 * 1, where we write the entire chain out at once. However, what if the number is 4, or 5, or 10, or 100?

We could generalize it as n! = n * n-1 * n-2 * etc etc * 1, or, strictly speaking, n! = n * n-1 * … * 1, with the three periods representing the implied intermediate values. As an easier shorthand, we can describe a factorial instead as n! = n * n-1!; this is a more exact representation of the verbal recipe we gave for arriving at a factorial – ‘multiply each whole number by the whole number preceding it, till we reach zero”. Defining an object in terms of a simpler case of itself is known as a recursive definition.

The thing is, though, doesn’t recursion go on forever? If Charlie Kaufman screenplays have taught us anything, it’s that the self-referential loop just goes backwards and backwards until we lose our minds.  Well, fear not, because just like an iterative loop, a recursion has a condition known as the base case that ends the loop. In the case of a factorial, !0 returns 1.

There’s an old joke that goes, “the key to understanding recursion is understanding recursion”. While humorous, this is, as far as I can tell, somewhat inaccurate, since there is no base case. In fact, in perhaps reinforces the false impression that recursion produces an infinite, self-referential loop. I would argue that a more useful reformulation would be “The key to understanding recursion is understanding recursion, unless you don’t understand recursion, in which case the key to understanding recursion is understanding the role of the base case, value-returning functions being treated as variables, and functions resolving first in, last out.” However, all that would probably not fit on a T-shirt.

#include <stdio.h>


int factorial(int n);

int main(void){
int n = 4;

printf("%d! = %d\n", n, factorial(n));

n--;

printf("%d! = %d\n", n, factorial(n));

return 0;

}


int factorial(int n){
//use a recursive function
if(n>1){
return n * factorial(n-1);
} else {
return 1;
}
}

One of the keys to grasping recursion in C is to remember that a value-returning function can be used in place of the value; this works because a called function must always resolve itself before the called function can resume executing.

Another fun example is to define the multiplication of positive integers recursively. Multiplication is, after all, just a weird kind of addition. If we take x * y, we see that it is really x plus itself y times.

#include <stdio.h>

int multiply(int x, int y);
//recursive version
int multiplyRecursively(int x, int y);

int main(void){
int n = 10;

for(int i = 1; i <= 10; i++, n--){
printf("%d * %d = %d\n", i, n, multiply(i, n));
printf("%d * %d = %d\n", i, n, multiplyRecursively(i, n));
}

return 0;
}

//iterative function
int multiply(int x, int y){
int val = x;
while(y-- > 1){
val+=x;
}
return val;
}

//recursive function
int multiplyRecursively(int x, int y){
if(y > 1){
return x + multiplyRecursively(x, y-1);
} else {
return x;
}
}

As our final example, we will take a look at the Fibonacci sequence.  The Fibonacci sequence is when we get a number by adding the two previous numbers in the sequence, and to start the sequence off, the first number is 0 and the second number is 1. Thus, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … We can view a Fibonacci sequence as being a function, we are willing to define f(0) as equalling 0 and f(1) as equalling 1; in other words, in the case of 0 or 1 the function returns its argument.

What about 2? Well, f(2) = 1 + 0, which also happens to be f(1) + f(0), so we can say that f(2) = f(1) + f(0). What about 3? Well, f(3) = 1 + 1, which happens to also be f(2) + f(1), thus we can say f(3) = f(2)+f(1), remembering here that f(2) = 1 and f(1) = 1. What about 4? Well, f(4) = 2 + 1, and since f(3) = 2 and f(2) = 1, we can say that f(4) = f(3) + f(2). For any element in the sequence, then, we can say that f(n) = f(n-1) + f(n-2), where f(0) = 0 and f(1) = 1. Or, if we really, really want to, we can say that f(n) = f(n-1) + f(n-2), where f(n) = n if n = 0 or n = 1.

#include <stdio.h>

int fib(int a);

int main(void){

for(int i = 0; i < 10; i++){
printf("Fib. num. for %d is %d\n", i, fib(i));
}

return 0;

}

int fib(int a){

if(a <= 1){
return a;
} else {
return fib(a-1) + fib(a-2);
}
}

Do you have $2.99 and a tablet, computer, or Kindle? Purchase a copy of my book on C, it’s viewable on just about any glowing screen you can think of. Over 100 example programs and explanations that are, I swear, far more lucid that the ones you find on this blog. http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/

 

 

 

Advertisements

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