無名関数(ラムダ)を再帰呼び出ししたくなることが稀によくあると思います。
そこで昨今ならば不動点コンビネータが定石かと思います。
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
その他、サイトで色々な情報を提供されている方々にも感謝です。
ありがとうございました。
Page Info | |
---|---|
Page Name : | 技術系備忘録/C++/小技/無名関数の再帰をローテクで |
Page aliases : | None |
Page owner : | takatsuka |
Can Read | |
Groups : | All visitors |
Users : | All visitors |
Can Edit | |
Groups : | No one |
Users : | No one |
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