Back to page

− Links

 Print 

技術系備忘録​/C++​/小技​/無名関数の再帰をローテクで :: シンクリッジ

xpwiki:技術系備忘録/C++/小技/無名関数の再帰をローテクで

無名関数(ラムダ)を再帰呼び出ししたくなることが稀によくあると思います。

そこで昨今ならば不動点コンビネータが定石かと思います。

int fibonacci(int n) {
	const auto Y = [](auto f) {
		return [=](auto... args) {
			return f(f, args...);
		};
	};
	auto f = Y([](auto f, int n)->int {
		return n < 2 ? n : f(f, n - 1) + f(f, n - 2);
	});
	return f(n);
}

int main() {
	std::cout << fibonacci(10) << std::endl;
}

Yコンビネータなる実装です。関数の引数で自分自身が与えられています。
これでまったく問題ありません。解決です。

がしかし唯一の弱点としては C++14 以上が必要になることです。

ですのでココでは C++14 未満でも使えるローテクな手段
その場にローカルクラス(構造体)と関数を定義し再帰呼び出し です。

int fibonacci(int n) {
	struct F {
		static int f(int n) {
			return n < 2 ? n : f(n - 1) + f(n - 2);
		}
	};
	return F::f(n);
}

コレの弱点としては

・ラムダではないのでキャプチャが使えない!(これはイタイ)
・つまり無名関数ではない!(・・・なので記事タイトルに偽りアリとのご指摘あればスミマセン)
・見てくれがダサい!(・・・個人の感想です)

などありますが、関数の外(スコープ)を汚すこともなく、
std::function も使わず(計ってはいませんが)遅くもなさそうで、
実はコレで十分な場合も多そうです。

ちなみに constexpr もイケます。

int rev(int n){
	struct F {
		static constexpr int f(int n) {
			return n < 2 ? n : f(n - 1) + f(n - 2);
		}
	};

	switch (n) {
	case F::f(3):	return 3;
	case F::f(4):	return 4;
	case F::f(5):	return 5;
	}
	return -1;
}





C++ は14や17になって色々と出来ることが増えてきましたが、
ローカルクラス自体は C++11 未満のコンパイラ、C++03 とかでも使えるハズなので有難く思うことがあるかもしれません。

なお、以下サイトの記事 "C++のラムダで再帰する" はとても充実しており大変参考になりました。
https://koturn.hatenablog.com/entry/2018/06/10/060000[1]

その他、サイトで色々な情報を提供されている方々にも感謝です。
ありがとうございました。


Last-modified: 2021-10-14 (Thu) 11:46:26 (JST) (409d) by takatsuka