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
%