NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/programm/2436

Text File | 1992-08-23 | 2.8 KB | 75 lines

Newsgroups: comp.programming
Path: sparky!uunet!cs.utexas.edu!torn!utzoo!telly!druid!pseudo!mjn
From: [e-mail] (Murray Nesbitt)
Subject: Re: Teaching the basics
Organization: Private system in Toronto, ON
Date: Sun, 23 Aug 1992 11:19:41 GMT
Message-ID: <[e-mail]>
In-Reply-To: [e-mail]'s message of Wed, 19 Aug 1992 15:48:30 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Sender: [e-mail] (Murray Nesbitt)
Lines: 62


[e-mail] (Hunk) writes:

>In article <[e-mail]> [e-mail] (Richard A. O'Keefe) writes:
>>If you don't know recursion, you don't know programming.  It is one of the
>>simpler concepts in computing.  (Much simpler than mutable variables, IMHO.)
>
>I think recursion is a farce.  And just to rub it in, here's the Towers of
>Hanoi (up to N = 31, I'm assuming long integers are 32 bits) without it (in C)

You are joking, right?  If not, I don't see how your example Hanoi
program strengthens your position that recursion is a ``farce''.

>/* Move a stack of N objects from tower A to C, using B */
>void Hanoi(int N, char A, char B, char C) {
>   unsigned long X = 0; char D;
>HANOI:
>   if (N > 0) {
>      D = B, B = C, C = D, N--;
>      X = 2*X + 2; goto HANOI; X2: X = (X - 1)/2;
>      N++, D = B, B = C, C = D;
>      printf("Move %d from %c to %c.\n", N, A, C);
>      D = A, A = B, B = D, N--;
>      X = 2*X + 1; goto HANOI; X1: X = (X - 1)/2;
>      N++, D = A, A = B, B = D;
>   }
>   if (X&1) goto X1;
>   if (X > 0) goto X2;
>}

An equivalent recursive version:

void Hanoi( int n, char start, char temp, char dest )
{
    if ( n ) {
        Hanoi( n - 1, start, dest, temp );
        printf( "Move %d from %c to %c.\n", n, start, dest );
        Hanoi( n - 1, temp, start, dest );
    }
}

Beauty is in the eye of the beholder, but in my opinion the recursive
version is a little easier to follow, to say the least.

On my system, both the native C compiler and gcc with optimization off
produce faster executables for the recursive version (although gcc -O
produces a faster iterative executable; strangely enough, gcc -O
actually slows down the recursive version).

On top of it all, the recursive version does not have an arbitrary
limit on the number of disks, and can be easily translated to any
language supporting recursion.

For some problems, it may be necessary to avoid (or reduce) recursion
in the interest of execution time.  But generally, if a recursive
solution to a problem is obvious, as is the case with Towers of Hanoi
(or binary tree traversal, etc.), it should be coded recursively.  The
clarity and elegance of a recursive solution will usually outweigh the
(possible) performance penalty.

--
Murray