計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Tree Recursion - iterative process

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.2(Functions and the Processes They Generate)、1.2.2(Tree Recursion)、Exercise 1.11の解答を求めてみる。

コード

function f(n) {
    return n < 3 ?
        n :
        f(n - 1) + 2 * f(n - 2) + 3 * f(n - 3);
}

function f1(n) {
    function iter(a, b, c, count) {
        return count === 0 ?
            c :
            count === 1 ?
                b :
                iter(a + 2 * b + 3 * c, a, b, count - 1);
    }
    return iter(2, 1, 0, n);
}
function log_iter(n, count) {
    if (n > count) {
        return;
    }
    console.log(f(n), f1(n));
    log_iter(n + 1, count);
}

function log(count) {
    log_iter(1, count);
}

log(20);

入出力結果(Terminal, Zsh)

% node answer1.11.js
1 1
2 2
4 4
11 11
25 25
59 59
142 142
335 335
796 796
1892 1892
4489 4489
10661 10661
25315 25315
60104 60104
142717 142717
338870 338870
804616 804616
1910507 1910507
4536349 4536349
10771211 10771211
%