アッカーマン関数

アッカーマン関数とは、原始帰納的関数 (原始再帰的関数) でない帰納的関数 (再帰的関数、計算可能関数) の実例として有名な関数です。 要するに、再帰で解かないと非常に面倒な関数のひとつなのですが、awk でも再帰関数を用いることができます。

#! /usr/bin/gawk -f
BEGIN {
    print ackermann(3, 4);
}

function ackermann(m, n) {
    if (m == 0) {
        return n + 1;
    } else if (m > 0 && n == 0) {
        return ackermann(m - 1, 1);
    } else if (m > 0 && n > 0) {
        return ackermann(m - 1, ackermann(m, n - 1));
    }
}

実行してみます。

$ gawk -f ackermann.awk
125

あまりにも引数が大きいとあっというまに計算時間が長くなるので注意してください。