Programming Recursion

2012 With Rz language (version 3.3)

This is a small introduction to recursive programming. You need to read to think along with this essay.
Recursion needs:
1) terminating case
2) recursive case with increasing/decreasing parameter(s)

Most important thing is choosing the parameters.

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

factorial(n)
if n == 0 return 1
else return n * factorial(n-1)

written in NUT as

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

2. summation from n to m

using n as increasing parameter and check its termination with m.
the recursive case is n + sum(n+1, m).

sum(n, m){
if( n == m ) return m;
else return n + sum( n+1, m);
}

3. We can also use an "accumulating parameter" to hold the intermediate result. This can turn a recursion into a special from called "tail-recursion".

using p to hold the intermediate result

sum2(n, m, p){
if( n == m ) return n+p;
else return sum2( n+1, m, n+p );
}

it is called with p starts at 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. n * m can be calculated by n + n + ... m times.

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

The recursion will go on for m times.

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

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

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

Every time we recurse, n is double, m is half. Start with the call mul2(n,m,n)
The mul2 is faster than mul by logarithmic order. This shows that improving the "algorithm" can yield very large gain.

Exercises (to try out your brain)

1. Here is the "strcpy" function. A string is an array of character (integer) terminated with a zero.

strcpy(s1 s2){    // copy from s2 to s1
i = 0;
while( s2[i] > 0 ){
    s1[i] = s2[i];
    i = i + 1;
}
s1[i] = 0;      // terminate with 0
}

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. 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 5 June 2012