再帰
たまに再帰は、計算機科学・プログラミング等の書物で、ジョークとして掲載される場合がある。そうした本では概して循環定義や自己参照が付されており、次のような馬鹿らしい項目が用語集として載っていることも珍しくない。
再帰については「再帰」を参照のこと。
これは想定した再帰段階が基底段階へと帰着することなく、無限後退を引き起こすという(プログラミング失敗例の)洒落である。この手の最初のジョークは1975-76年に出版されたプログラム言語の教本『Let's talk Lisp 』と『in Software Tools』に見られる。これは関数型プログラミングを伝授する一環としての洒落で、上の書籍が出版される前に(米国の)プログラミング関連コミュニティで既に広まっていた。
もう一つの冗談が「再帰を理解するには、再帰を理解する必要がある」というものである。英語版Googleウェブ検索エンジンで"recursion"を検索すると、同サイトでは一番上に"Did you mean: recursion(再帰って意味だったかな)"と赤く表示される。
再帰的頭字語は、再帰を含んだ洒落の例である。例えば、PHP (プログラミング言語)は"PHP Hypertext Preprocessor"の略で、WINEは"WINE Is Not an Emulator"、GNUは"GNU's not Unix"を表す。
単純化の一般的な方法は、問題を同じ種類の小問に分割することである。コンピュータプログラミングの技法としてこれは分割統治法と呼ばれ、多くの重要なアルゴリズム設計の鍵となる。分割統治法は、問題解決へのトップダウン型アプローチとして機能し、そこでは問題がより小さなインスタンスを解決することにより解決される。反対のアプローチ手法は動的計画法である。こちらはボトムアップ型アプローチとして機能し、目的の規模に達するまでより大きなインスタンスを解決することによって問題が解決される。
プログラミングの観点では、nを表現するのにn-1という参照を持ち出してくるものを「再帰」という。再帰の古典的な例としては、C言語で与えられた階乗関数の定義がある。
この関数では、掛け算のため入力自身より小さな(n-1)という参照を再帰的に呼び出し、再帰呼び出しの結果にnを掛ける処理を、階乗の数学的定義と同じく基底段階の値に達するまで実行する。
アルゴリズムにおける再帰の使用には、長所も短所もある。主な長所は、一般に命令の単純さである。主な短所は、自身を呼び出す手法なので引数が再帰終了条件を満たさない状況を避けるよう値の変化に注意する必要があること。また、再帰アルゴリズムのメモリ使用量が著しく激増して負荷ががかかるため、大規模なインスタンスを扱うには非実用的な点である。