Programming Recursion (C version)

This is a gentle introduction to programming using recursion. You need to read and think along with this essay. It takes about one hour to hone your skill. Get your favourite C compiler and IDE ready!

Key idea

Recursion needs:
1) terminating case
2) recursive case with increasing/decreasing parameter(s)

Most important thing is choosing the parameters.

Examples

1. Simple recursion, follow a recursive definition. For example,

#include <stdio.h>

int factorial(n){
if(n == 0) return 1;
else return n * factorial(n-1);
}

int main(void){
printf("%d\n",factorial(6));
}

The termination case is when n = 0 and the recursive case is n * factorial(n-1). Try it on your favourite C compiler and see the result.

2. Summation from a to b

Using a as increasing parameter and check its termination with a = b.
the recursive case is a + sum(a+1, b).

int sum(int a, int b){
if(a == b) return b;
else return a + sum(a+1,b);
}

int main(void){
printf("%d\n",sum(1,10));
}

3. We can also use an "accumulating parameter" to hold the intermidiate result. This can turn a recursion into a special from called "tail-recursion" (which a compiler can make an efficient code). Using s to hold the intermediate result. We start with s = 0. Becareful at the termination, the last number needs to be sum too.

int sum2(int a, int b, int s){
if(a == b) return s+b;
else return sum2(a+1,b,s+a);
}

int main(void){
printf("%d\n",sum2(1,10,0));
}

The "tail-recursion" is more efficient than a general recursion form because the last recursive call can be turned into a "goto-beginning" hence saving a function call (and stack space). This makes recursion as fast as a loop. (This tail-call can be detected and exploited by any modern compiler).

4. Now we can try another problem. Doing multiplication by repeat addition. m * n can be calculated by m + m + ... n times.

int mul(int m, int n){
if(n == 1) return m;
else return m + mul(m,n-1);
}

The recursion will go on for n times.

5. We can do better by rearranging the recurrence definition. If we do grouping (m + m) = 2m and
2m + 2m + .. It will need only n/2 times. We repeat doing this:
4m + 4m + .. n/4 times.
...
nm ... n/n or 1 times.

The m * n will need only log_2 n times of loop. This is much faster.
using p to hold the intermediate result.

int mul2(int m, int n, int p){
if(n == 1) return p;
else return mul2(m+m, n/2, p+m);
}

Everytime we recurse, m is double, n is half. Of course, it only works with n = 2^k (n = 2,4,8,16...). It starts with p = m.
The mul2 is faster than mul by logarithmic order. This shows that improving the "algorithm" can yield very large gain.

6. You can use recursion with an array. The recursion is on the index. We try the sum again. Summation of all elements in an array. Let the last element be 0. (it is called a sentinel).

int ax[] = {11,22,33,44,55,0};

int suma(int i){
if(ax[i] == 0) return 0;
else return ax[i] + suma(i+1);
}

int main(void){
printf("%d\n",suma(0));
}

7. Using similar style (recurse on index), you can find a maximum value in an array.

int max(int a, int b){
    return (a > b) ? a : b;
}

int maxa(int i){
    if(ax[i] == 0) return 0;
    else return max( ax[i], maxa(i+1) );
}

What it does is it expands into : max( ax[0], max( ax[1], max( ax[2] ... )

Exercises (to try out your brain)

1. Here is the "copystring" function. A string is an array of character terminated with a zero.

char s1[] = "abcdef";
char s2[100];

/* copy string s1 to s2 */
void copystring(char *s2, char *s1){
    int i;
    i = 0;
    while(s1[i] != 0){
        s2[i] = s1[i];
        i = i + 1;
    }
    s2[i] = 0;
}

int main(void){
    copystring(s2,s1);
    printf("%s\n",s2);
}

Write a recursive version of it.

2. Write a recursive function to reverse a string.
3. Do you know a Fibonacci number. A simple implementation will be very inefficient. Write a recursive function using an accumalating parameter will turn that into a very efficient program.
4. Using recusion on index similar to example 6 and 7, write a program to find whether an array contains a particular number.
5. The fun bit of recursion is when you use it to "build" a list. It is very elegant. Think how you can write an "append" function using recursion. It is beautiful.

Prabhas Chongstitvatana
last update 28 Septermber 2011