メニュー
ブログ更新履歴
コンテンツ更新履歴
リンク
  • rlib-MML WebApp
  • MML (Music Macro Language) をコンパイルし、再生やファイル出力(MP4、標準MIDIファイル)をブラウザ上で行えます。
  • Magome
  • クラウドベースのMIDIシーケンサ
    音楽制作に興味のある方を対象に、スタンドアロンでも使え、ネットならではの面白さも兼ね備えた音楽制作アプリの提供を目指しています。
twitter

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

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

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

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


Front page   Freeze Diff Backup Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help   RSS of recent changes (RSS 1.0) RSS of recent changes (RSS 2.0) RSS of recent changes (RSS Atom) Powered by xpWiki
Counter: 2788, today: 3, yesterday: 0
Princeps date: 2021-10-14 (Thu) 10:56:28
Last-modified: 2021-10-14 (Thu) 11:46:26 (JST) (1155d) by takatsuka