The Ackermann Function

[swampyankee]

Just for grins, I decided to code Ackerman's function in Perl.

The definition is really quite simple:

Formal Definition:
* A(0, j)=j+1 for j ≥ 0
* A(i, 0)=A(i-1, 1) for i > 0
* A(i, j)=A(i-1, A(i, j-1)) for i, j > 0

In my typical Brute Force and Ignorance™ method, I coded this:

#!perl

use strict;
use warnings;

use bigint;

my  $value;

my $m;
my $n;

if($#ARGV >= 1){
    $m = shift(@ARGV);
    $n = shift(@ARGV);
    }
elsif($#ARGV == 0){
    $m = shift(@ARGV);
    $n = 0;
    }
else{
    $m = 0;
    $n = 0;
    }

$value = ackermann($m, $n);

print "ackermann( $m, $n ) is $value\n";

sub ackermann {

    (my $m, my $n) = @_;

    if($m == 0){
        return $n+1;
    }
    elsif($m > 0 and $n == 0) {
        return ackermann($m - 1, 1);
    }
    elsif($m > 00 && $n > 0){
        return ackermann($m-1, ackermann($m, $n-1));
    }
}

When run as ackermann 4 1, I get (many) 'deep recursion' messages.

OK; I know that my implementation is less than brilliant; that's not my question.

This is my question: Is there any way of predicting what conditions are likely to result in deep recursion messages?

---

added in edit

Thanks to ikegami (I've got to try Memoize) and jdhedden.

[ikegami]

The following is perldiag's description of this warning:

This subroutine has called itself (directly or indirectly) 100 times more than it has returned. This probably indicates an infinite recursion, unless you're writing strange benchmark programs, in which case it indicates something else.

If the deep recursion is expected — it is — you can remove the warning using no warnings 'recursion';

To speed things up (by omitting redundant calls) at the expense of memory, use Memoize to cache results.

By the way, your @ARGV code can be simplified to:

my $m = shift || 0;
my $n = shift || 0;

[ikegami]

The results of memoizing (without actually using Memoize) are:

ackermann(0..3, 4)

swampyankee: ok
ikegami:     ok

Benchmark: timing 1000 iterations of ikegami, swampyankee...
   ikegami:  6 wallclock secs ( 4.54 usr +  0.00 sys =  4.54 CPU) @ 22
+0.46/s (n=1000)
swampyankee: 49 wallclock secs (35.96 usr +  0.02 sys = 35.98 CPU) @ 2
+7.79/s (n=1000)

              Rate swampyankee     ikegami
swampyankee 26.8/s          --        -88%
ikegami      220/s        724%          --

Code:

Read more... (2 kB)

[jdhedden]

Perl complains after a code depth of 100. As far as predicting goes, you have to analyze the code yourself to determine if you're ever going to hit that level.

[Moron]

The way I know is to make a finite state diagram, (see also finite state machine)- in this case the thread moves into three possible states controlled by the ifs in the subroutine, plus a 'final return' state and you would need to identify for each state what conditions result in movement between the states. The fact that branch three generates two calls - one that routes to branch two and one back to branch three means that a thread in state three cannot attain the 'final return' state for the example data. Use the possible data ranges to fill out the state transition table described in the link above to identify which boundary conditions lead to final exit and which not.

[gjb]

I'm afraid this doesn't make sense to me. Are you suggesting that the Ackermann function should simply not be computed if the conditions for branch 3 hold? That would imply that one can only compute A(0, i) and A(i, 0), which is not particularly interesting.

I may miss your point, but I'd be a bit surprised if FSMs would be useful in this context. Can you show us what you have in mind?

Just my 2 cents, -gjb-

[NetWallah]

Oh - I beg to differ - His Noodly Appendage, the FSM is relevent in EVERY context !

[NateTut]

Hey, you can't trademark "Brute Force and Ignorance" they are traditional techniques in use since the dawn of mankind.

[swampyankee]

I can't?

This in a country (USA) where somebody recently got a patent for the wheelbarrow?

Drat!