Month: August 2009

A lot has been written on the use of recursion in computer programming, yet it remains one of the least understood aspects – especially for beginners. Having visited the Wikipedia page on recursion, I believe the text is hard to understand, and the examples are forced: there is no reason to use recursion to solve Fibonacci series or calculate factorials.

Recursion means solving a problem by splitting it into smaller problems. If the problem is numerical, then splitting it into smaller numbers.

Consider the problem of creating all permutations of a character in a string. If ‘abc’ is input, the program should show ‘abc’,’acb’,’bac’,… and so on. How can we solve this problem?

We propose to write a function called ‘permute’ which creates permutations of the string that is passed to it. When I wanted to create this function, the first thing I did is to design the tree. Just doing this showed me a flaw in the initial design that I was planning, and later helped me with the debugging. The tree shows that each letter in the input string is extracted from the string one by one, and the rest of the string is passed again as parameter to the same function – the character removed is added to the prefix. Eventually the ‘string parameter’ becomes a single character at which time the permutation is printed.

Have a look at the code, and relate it to the tree:

#!/usr/bin/perl

print("Please enter a string to permute->");
$s = ;
chomp($s);

permute ($s,length($s),"","");

sub permute {
    my ($s,$l,$pref)=@_;
    my $i;

    if ($l > 1) {
        for ($i = 0; $i < $l; $i++) {
            $ch = substr($s,$i,1);
            $rest = substr($s,0,$i) . substr($s,$i+1,$l);
            permute($rest,$l-1,$pref . $ch);
        }
    }
    else {
        print $pref . $s . $sufx . "\n";
    }
}

As I said the first step in such recursive coding is to identify the tree. When I started out, I made the tree in an incorrect fashion. I split permute(abc) into a.permute(bc) and permute(bc).a. I felt that since the basic idea was to permute, this is how we should do it. However, doing this resulted in only four permutations at the bottom of the tree, instead of six as should be. This made me go back to the drawing board.

I want to end this on a humorous note for people who write recursive solutions to simple problems:

To loop is human, to recur - divine.