手作業による末尾呼び出し最適化
template<typename T> class tail_rec { public: tail_rec(const T& value): value(value), next(nullptr) {} tail_rec(std::function<tail_rec()> next): next(next) {} T get() const { tail_rec tr = *this; while (tr.next) { tr = tr.next(); } return tr.value; } private: T value; std::function<tail_rec()> next; }; int simple_sum(int n) { if (n == 0) return 0; return n + simple_sum(n - 1); } tail_rec<int> sum_tr(int n, int m) { if (n == 0) return tail_rec<int>(m); return tail_rec<int>([=]() { return sum_tr(n - 1, n + m); }); } int sum_tr(int n) { return sum_tr(n, 0).get(); }
ようやっと、再帰呼出しやリターンを関数オブジェクトの生成に置き換え、呼び出し元でのget呼び出しで繰り返し処理する(ことで、スタックが深まっていかない)ことが解りました。上記のコードにはでてきませんが、継続渡しによる末尾呼び出し化も覚えることができました。感謝。