計算機科学のブログ

Building Abstractions with Functions - The Elements of Programming - Linear Recursion and Iteration - Ackermann's function, concise mathematical definitions

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.1(The Elements of Programming)、1.2.1(Linear Recursion and Iteration)、Exercise 1.10の解答を求めてみる。

コード

function A(x, y) {
    return y === 0 ?
        0 :
        x === 0 ?
            2 * y :
            y === 1 ?
                2 :
                A(x - 1, A(x, y - 1));
}

console.log(A(1, 10));
console.log(A(2, 4));
console.log(A(3, 3));

function f(n) {
    return A(0, n);
}
function f1(n) {
    return 2 * n;
}

console.log('f')
console.log(f(1), f1(1));
console.log(f(2), f1(2));
console.log(f(3), f1(3));
console.log(f(4), f1(4));
console.log(f(5), f1(5));

function g(n) {
    return A(1, n);
}
function g1(n) {
    return 2 ** n;
}

console.log('g')
console.log(g(1), g1(1));
console.log(g(2), g1(2));
console.log(g(3), g1(3));
console.log(g(4), g1(4));
console.log(g(5), g1(5));

function h(n) {
    return A(2, n);
}
function h1(n) {
    // 2^(2^(2^(2^…))
    function iter(counter, result) {
        if (counter === n) {
            return result;
        }
        return iter(counter + 1, 2 ** result)
    }
    return iter(0, 1);
}

console.log('h')
console.log(h(1), h1(1));
console.log(h(2), h1(2));
console.log(h(3), h1(3));
console.log(h(4), h1(4));
// console.log(h(5), h1(5));

入出力結果(Terminal, Zsh)

% node answer1.10.js
1024
65536
65536
f
2 2
4 4
6 6
8 8
10 10
g
2 2
4 4
8 8
16 16
32 32
h
2 2
4 4
16 16
65536 65536
%