ページへ戻る

− Links

 印刷 

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

xpwiki:技術系備忘録/C++/小技/無名関数の再帰をローテクで の変更点
« Prev[3]  
1: 2021-10-14 (木) 10:56:28 takatsuka[4] ソース[5] 現: 2021-10-14 (木) 11:46:26 takatsuka[4] ソース[6]
Line 1: Line 1:
- 準備中+無名関数(ラムダ)を再帰呼び出ししたくなることが稀によくあると思います。 
 + 
 +そこで昨今ならば不動点コンビネータが定石かと思います。 
 + 
 +#prettify{{ 
 +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 未満でも使えるローテクな手段 
 +''その場にローカルクラス(構造体)と関数を定義し再帰呼び出し'' です。 
 +#prettify{{ 
 +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 もイケます。 
 +#prettify{{ 
 +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 
 + 
 +その他、サイトで色々な情報を提供されている方々にも感謝です。 
 +ありがとうございました。
« Prev[3]  
ページ別名: 未設定
ページ作成: takatsuka
サイト管理: takatsuka

Links list

(This host) = https://thinkridge.com

  1. (This host)/modules/xpwiki/index.php?cmd=backup&pgid=110&age=Cur&action=source
  2. (This host)/modules/xpwiki/?%E6%8A%80%E8%A1%93%E7%B3%BB%E5%82%99%E5%BF%98%E9%8C%B2%2FC%2B%2B%2F%E5%B0%8F%E6%8A%80%2F%E7%84%A1%E5%90%8D%E9%96%A2%E6%95%B0%E3%81%AE%E5%86%8D%E5%B8%B0%E3%82%92%E3%83%AD%E3%83%BC%E3%83%86%E3%82%AF%E3%81%A7
  3. (This host)/modules/xpwiki/index.php?cmd=backup&pgid=110&action=diff&age=1
  4. (This host)/userinfo.php?uid=1
  5. (This host)/modules/xpwiki/?cmd=backup&pgid=110&action=source&age=1
  6. (This host)/modules/xpwiki/?cmd=backup&pgid=110&action=source&age=Cur
  7. (This host)/modules/xpwiki/index.php?cmd=backup&pgid=110
  8. (This host)/modules/xpwiki/index.php?cmd=backup&action=diff&pgid=110&age=1