手作業による末尾呼び出し最適化

ここで紹介されている方法をC++で書きなおしてみました。

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呼び出しで繰り返し処理する（ことで、スタックが深まっていかない）ことが解りました。上記のコードにはでてきませんが、継続渡しによる末尾呼び出し化も覚えることができました。感謝。