There's more than one way to do things PerlMonks

### Re: Recursion: An example of Looping and Recursion

by lolindrath (Scribe)
 on Nov 16, 2000 at 07:15 UTC ( #41936=note: print w/replies, xml ) Need Help??

This is the Euclidean algorithm for finding the Greatest common divisor between two numbers. I thought I'd throw a bit of my own code into the fray. The first one uses a loop, the second uses recursion. Could someone benchmark this for me?
```#!/usr/bin/perl -w

print "GCD: " . GCD( 45, 5 ) . " RecGCD: " . RecGCD( 45, 5 ) . "\n";

#Assumes \$A is the largest number
sub GCD
{
\$A = shift;
\$B = shift;
\$R = 1;

while ( \$R != 0 )
{
\$R = \$A % \$B;

if ( \$R == 0 )
{
return \$B;
}

\$A = \$B;
\$B = \$R;
}
}

#Assumes \$A is the largest number
sub RecGCD
{
\$A = shift;
\$B = shift;
\$R = 0;

\$R = \$A % \$B;

if ( \$R == 0 )
{
return \$B;
}

RecGCD( \$B, \$R );
}

--=Lolindrath=--

Replies are listed 'Best First'.
Re: Re: Recursion: An example of Looping and Recursion
by extremely (Priest) on Nov 16, 2000 at 11:08 UTC
Whoop! a benchmark question! Ahhh...
```# for 45, 5
Rate  loop recur
loop  30118/s    --  -37%
recur 47528/s   58%    --

# for 296, 111
Rate recur  loop
recur  9303/s    --  -36%
loop  14426/s   55%    --

# for 298, 111
Rate recur  loop
recur 4672/s    --  -45%
loop  8445/s   81%    --```

Interesting what a win the loop version is on that last one...

--
\$you = new YOU;
honk() if \$you->love(perl)

Create A New User
Node Status?
node history
Node Type: note [id://41936]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (8)
As of 2018-01-17 12:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (198 votes). Check out past polls.

Notices?