Programming Recursion

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

(def factorial n ()
(if (= n 0) 1
(* 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).

(def sum (n m) ()
(if (= n m) m
(+ n (sum (+ n 1) m))))

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".

using p to hold the intermediate result

(def sum2 (n m p) ()
(if (= n m) p
(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.

(def mul (n m) ()
(if (= m 1) n
(+ 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.

(def mul2 (n m p) ()
(if (= m 1) p
(mul2 (+ n n) (/ m 2) (+ n p))))

Everytime we recurse, n is double, m is half.
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.

(def strcpy (s1 s2) (i)
(do
(set i 0)
(while (neq (vec s2 i) 0)
(do
(setv s1 i (vec s2 i))
(set i (+ i 1))))
(setv s1 i 0))) // terminate s1 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 8 June 2010