再帰呼び出し
|
Topic path:
Top
/
授業
/
C言語基礎
/ 再帰呼び出し
-- 雛形とするページ --
BracketName
FormattingRules
FrontPage
Help
InterWiki
InterWikiName
InterWikiSandBox
MenuBar
PHP
PukiWiki
PukiWiki/1.4
PukiWiki/1.4/Manual
PukiWiki/1.4/Manual/Plugin
PukiWiki/1.4/Manual/Plugin/A-D
PukiWiki/1.4/Manual/Plugin/E-G
PukiWiki/1.4/Manual/Plugin/H-K
PukiWiki/1.4/Manual/Plugin/L-N
PukiWiki/1.4/Manual/Plugin/O-R
PukiWiki/1.4/Manual/Plugin/S-U
PukiWiki/1.4/Manual/Plugin/V-Z
SandBox
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
その他
その他/GnuplotでKeynote風のグラフを作成する
その他/Javaの参考文献
その他/LaTeXの参考文献
その他/MacでGnuplotを使う
その他/MacでLEGO MINDSTORMSの開発環境NXCを使う
その他/MacでLet's Encryptを使う
その他/MacでPython 3を使う
その他/MacでRuby 1.9を使う
その他/MacでTeXを使う
その他/MacでTeXを使う(旧)
その他/MacでWindowsを使う
その他/Macでパスを通す
その他/Macで実験結果をまとめる
その他/Mailmanのメーリング・リストをバーチャル・ホストに移行する
その他/PostfixでSMTP AUTH over TLSを使う
その他/Prologの参考文献
その他/PukiWikiで一部のページへのアクセスを制限する
その他/PukiWikiで日本語で始まるページのタイトルが表示できない問題を解決する
その他/Rubyの参考文献
その他/Rの参考文献
その他/Snow LeopardでGnuplotを使う
その他/VBAの参考文献
その他/WindowsでLEGO MINDSTORMSの開発環境NXCを使う
その他/patchファイルの作り方とpatchの当て方
その他/アルゴリズムの参考文献
その他/プレゼンテーションの参考文献
その他/人工知能の参考文献
その他/卒業研究を始める前に読んでおくべき3つのマンガ
その他/臨床工学に関するTEDプレゼンテーション
その他/論文執筆の参考文献
テキスト・マイニング
テキスト・マイニング/MacでHyper Estraierを使う
テキスト・マイニング/MacでMeCabを使う
テキスト・マイニング/MacでMySQLを使う
テキスト・マイニング/MacでNamazuを使う
テキスト・マイニング/MacでSennaを使う
テキスト・マイニング/MacでTermExtractを使う
テキスト・マイニング/MacでTokyo Dystopiaを使う
テキスト・マイニング/SennaのRubyバインディングを使う
テキスト・マイニング/テキスト分類による市場予測
テキスト・マイニング/テキスト回帰分析
テキスト・マイニング/参考文献
テキスト・マイニング/国際会議
データ・マイニング
データ・マイニング/Macでpandasとscikit-learnとJupyter Notebookを使う
データ・マイニング/Rでグラフを重ねる
データ・マイニング/Rでネットワーク構造を可視化する
データ・マイニング/TEDプレゼンテーション
データ・マイニング/データ・マイニングに関するTEDプレゼンテーション
データ・マイニング/参考文献
データ・マイニング/国際会議
バイオ・データ・マイニング
バイオ・データ・マイニング/BLASTで相同性検索を行う
バイオ・データ・マイニング/ClustalWでペアワイズ・アラインメントを行う
バイオ・データ・マイニング/ClustalWで多重アラインメントを行う
バイオ・データ・マイニング/DNAマイクロアレイ・データを解析する
バイオ・データ・マイニング/FASTAフォーマット
バイオ・データ・マイニング/HMMERで相同性検索を行う
バイオ・データ・マイニング/MacでBioPythonを使う
バイオ・データ・マイニング/MacでClustalWを使う
バイオ・データ・マイニング/MacでHMMERを使う
バイオ・データ・マイニング/RでNaïve Bayesを使う
バイオ・データ・マイニング/RでRandom Forestを使う
バイオ・データ・マイニング/RでSVMを使う
バイオ・データ・マイニング/Rでk平均法を使う
バイオ・データ・マイニング/Rでスペクトラル・クラスタリングを使う
バイオ・データ・マイニング/Rでデータを読み込む
バイオ・データ・マイニング/Rでマイクロアレイ・データを使う
バイオ・データ・マイニング/Rで主成分分析する
バイオ・データ・マイニング/Rで回帰分析する
バイオ・データ・マイニング/Rで決定木を使う
バイオ・データ・マイニング/Rで混合ガウス分布推定を使う
バイオ・データ・マイニング/Rで独立成分分析する
バイオ・データ・マイニング/Rで相関分析する
バイオ・データ・マイニング/Rで統計分析する
バイオ・データ・マイニング/Rで階層クラスタリングを使う
バイオ・データ・マイニング/Rで非線形回帰分析する
バイオ・データ・マイニング/Rの基本
バイオ・データ・マイニング/アミノ酸の条件付き生起確率を調べる
バイオ・データ・マイニング/アミノ酸の生起確率を調べる
バイオ・データ・マイニング/バイオ・データ・マイニングの参考文献
バイオ・データ・マイニング/人工的なたんぱく質データを生成する
人工知能
人工知能/TEDプレゼンテーション
人工知能/人工知能に関するTEDプレゼンテーション
人工知能/人工知能の参考文献
医療データ・マイニング
医療データ・マイニング/Rで心電図データを解析する
医療データ・マイニング/医療データ・マイニングの参考文献
医療データ・マイニング/医療データ・マイニングの論文
強化学習
強化学習/ColaboratoryでOpenAI Gymを使う
強化学習/ICML 2010 ワークショップ「強化学習と大規模探索」
強化学習/LEGO MINDSTORMS EV3でPythonを使う
強化学習/LEGO MINDSTORMS EV3で強化学習する
強化学習/MLJ Special Issue on Empirical Evaluations in Reinforcement Learning
強化学習/MacでOpenAI Gymを使う
強化学習/MacでRL-Glueを使う
強化学習/Pythonで強化学習する
強化学習/WindowsでOpenAI Gymを使う
強化学習/ファイナンスへの応用
強化学習/リスク回避強化学習
強化学習/人工知能における不確実性国際会議 UAI 2009
強化学習/人工知能合同国際会議 IJCAI-09
強化学習/平均報酬強化学習
強化学習/強化学習における知識の転移
強化学習/強化学習に関する総合的(学際的・分野横断的)シンポジウム MSRL
強化学習/強化学習のプログラムを作るときの注意点
強化学習/強化学習の参考文献
強化学習/強化学習の論文
強化学習/強化学習の論文を探す
強化学習/強化学習コンペ RL Competition 2009
強化学習/機械学習国際会議 ICML
強化学習/機械学習国際会議 ICML 2009
強化学習/機械学習国際会議 ICML 2010
強化学習/機械学習研究ジャーナル JMLR
強化学習/神経情報処理システム国際会議 NIPS
強化学習/神経情報処理システム国際会議 NIPS 2009
強化学習/自律型エージェントとマルチエージェント・システム国際会議 AAMAS 2009
強化学習/複利型強化学習
強化学習/計算言語学会年次会議・自然言語処理合同国際会議 ACL-IJNLP 2009
授業
授業/C言語基礎
授業/C言語基礎/C言語の構文
授業/C言語基礎/Linuxコマンドの復習
授業/C言語基礎/do-while文
授業/C言語基礎/for文
授業/C言語基礎/for文/練習問題
授業/C言語基礎/for文/練習問題/05A-1
授業/C言語基礎/for文/練習問題/05A-2
授業/C言語基礎/for文/練習問題/05A-3
授業/C言語基礎/for文/練習問題/05A-4
授業/C言語基礎/for文/練習問題/05A-5
授業/C言語基礎/if文
授業/C言語基礎/if文/練習問題
授業/C言語基礎/if文/練習問題/03A-1
授業/C言語基礎/if文/練習問題/03A-2
授業/C言語基礎/if文/練習問題/03A-3
授業/C言語基礎/switch文
授業/C言語基礎/while文
授業/C言語基礎/while文/練習問題
授業/C言語基礎/while文/練習問題/06A-1
授業/C言語基礎/while文/練習問題/06A-2
授業/C言語基礎/while文/練習問題/06A-3
授業/C言語基礎/while文/練習問題/06A-4
授業/C言語基礎/じゃんけんゲーム
授業/C言語基礎/キーボードからの入力
授業/C言語基礎/キーボードからの入力/練習問題
授業/C言語基礎/キーボードからの入力/練習問題/04B-1
授業/C言語基礎/キーボードからの入力/練習問題/04B-2
授業/C言語基礎/コンパイルとリンク
授業/C言語基礎/コンパイルと実行
授業/C言語基礎/スピード計算ゲーム
授業/C言語基礎/タイピング・ゲーム
授業/C言語基礎/プログラミングを学ぶための心構え
授業/C言語基礎/プログラムの作成と実行
授業/C言語基礎/プロトタイプ宣言
授業/C言語基礎/プロトタイプ宣言/練習問題
授業/C言語基礎/ライブラリー
授業/C言語基礎/ルーブリック
授業/C言語基礎/値渡しと参照渡し
授業/C言語基礎/値渡しと参照渡し/練習問題
授業/C言語基礎/再帰呼び出し
授業/C言語基礎/再帰呼び出し/練習問題
授業/C言語基礎/前処理
授業/C言語基礎/変数
授業/C言語基礎/変数/練習問題
授業/C言語基礎/変数/練習問題/02A-1
授業/C言語基礎/変数/練習問題/02A-2
授業/C言語基礎/変数/練習問題/02A-3
授業/C言語基礎/変数の高度な使い方
授業/C言語基礎/変数の高度な使い方/練習問題
授業/C言語基礎/変数の高度な使い方/練習問題の解答例
授業/C言語基礎/教科書と参考書
授業/C言語基礎/数当てゲーム
授業/C言語基礎/文字
授業/C言語基礎/文字コードと改行コード
授業/C言語基礎/文字列
授業/C言語基礎/文字列/練習問題
授業/C言語基礎/文字列/練習問題/10B-01
授業/C言語基礎/文字列/練習問題/10B-02
授業/C言語基礎/文字列/練習問題/10B-03
授業/C言語基礎/文字列/練習問題/10B-04
授業/C言語基礎/条件演算子
授業/C言語基礎/演算
授業/C言語基礎/演算/練習問題
授業/C言語基礎/演算/練習問題/02B-1
授業/C言語基礎/演算/練習問題/02B-2
授業/C言語基礎/演算/練習問題/02B-3
授業/C言語基礎/演算/練習問題/02B-4
授業/C言語基礎/演算/練習問題/02B-5
授業/C言語基礎/演算/練習問題/02B-6
授業/C言語基礎/演算子の高度な使い方
授業/C言語基礎/画面への出力
授業/C言語基礎/画面への出力/練習問題
授業/C言語基礎/画面への出力/練習問題/04A-1
授業/C言語基礎/画面への出力/練習問題/04A-2
授業/C言語基礎/画面への出力/練習問題/04A-3
授業/C言語基礎/計算ゲーム
授業/C言語基礎/課題の提出方法
授業/C言語基礎/課題提出についての注意事項
授業/C言語基礎/配列
授業/C言語基礎/配列/練習問題
授業/C言語基礎/配列/練習問題の解答例
授業/C言語基礎/関数
授業/C言語基礎/関数/練習問題
授業/バイオインフォマティクス特論
授業/バイオインフォマティクス特論/分析練習用データ
授業/情報技術英語B
授業/知能情報工学
機械学習
機械学習/Colabでデータ・サイエンス
機械学習/GeForce GTX 1080を搭載したMac ProでTensorFlowを使う
機械学習/MacでLIBLINEARを使う
機械学習/MacでLIBSVMを使う
機械学習/MacでMahoutを使う
機械学習/MacでRのkernlabパッケージを使う
機械学習/MacでRを使う
機械学習/MacでSVM-Lightを使う
機械学習/MacでTensorFlowを使う
機械学習/Macでpandasとscikit-learnとJupyter Notebookを使う
機械学習/Pythonでデータ分析するはじめの一歩(Mac編)
機械学習/Pythonでデータ分析するはじめの一歩(Windows編)
機械学習/Pythonでデータ分析する次の一歩(ディープ・ラーニング、Keras編)
機械学習/Pythonでデータ分析する次の一歩(データ分析支援ライブラリー、pandas編)
機械学習/Pythonでデータ分析する次の一歩(プログラミング言語、Python編)
機械学習/Pythonでデータ分析する次の一歩(実行環境、Jupyter Notebook編)
機械学習/Pythonでデータ分析する次の一歩(数値計算ライブラリー、NumPy編)
機械学習/Pythonでデータ分析する次の一歩(機械学習ライブラリー、scikit-learn編)
機械学習/Pythonで前処理する
機械学習/Pythonで学習パラメーターを最適化する
機械学習/Pythonで決定木を使う
機械学習/Pythonで特徴を選択する
機械学習/Pythonで説明変数の数を減らす
機械学習/Pythonで説明変数を減らす
機械学習/Rで大規模データを扱う
機械学習/WindowsでRを使う
機械学習/pandasとscikit-learnとJupyter Notebookで学習パラメーターを最適化する
機械学習/pandasとscikit-learnとJupyter Notebookで決定木を使う
機械学習/機械学習の参考文献
機械学習/機械学習の国際会議
機械学習/機械学習の論文を探す
金融データ・マイニング
金融データ・マイニング/TEDプレゼンテーション
金融データ・マイニング/時系列解析の参考文献
金融データ・マイニング/論文
ある関数の中でその関数自身を呼び出すことを''再帰呼び出し''といいます。 再帰呼び出しを用いると簡潔なプログラムにできる場合がありますが、再帰呼び出しには注意しなければならないこともあります。 ここでは、再帰呼び出しについて説明します。 *再帰的定義 [#ne8f32b9] [math]1[/math] から [math]n[/math] までの整数の和 [math]S_n[/math] について考えてみます。 \[ S_n = 1 + 2 + 3 + \dots + (n - 1) + n \] [math]S_n[/math] は、[math]1[/math] から [math]n-1[/math] までの整数の和 [math]S_{n-1}[/math] に [math]n[/math] を加えたものと考えることができます。 したがって、[math]S_n[/math] は、[math]S_{n-1}[/math] を使って次のように定義できます。 \[ \begin{align} S_n &= \left( 1 + 2 + 3 + \dots + (n - 1) \right) + n \\ &= S_{n-1} + n \end{align} \] このような定義を''再帰的定義''といいます。 ただし、[math]n = 1[/math]のときは [math]S_1 = 1[/math] です。 再帰的に定義された関数を''再帰関数''といい、再帰関数が関数の中で自分自身を呼び出すことを''再帰呼び出し''といいます。 整数の和を求めるプログラムを再帰呼び出しを使って書くと、次のようになります(プログラム1)。 #geshi(c){{ /* * 1からnまでの整数の合計を求める(再帰関数) */ int sum(int n) { if (n == 1) { return 1; } else { return sum(n - 1) + n; // 再帰呼び出し } } int main(void) { int i = sum(5); printf("%d\n", i); return 0; } }} 関数sumは、条件演算子を使って次のようにも書けます(プログラム2)。 #geshi(c){{ int sum(int n) { return n ? sum(n - 1) + n : 0; } }} n が 0 でないときは条件を満たすとして sum(n - 1) + n を計算して返します。 そうでないときは 0 を返します。 元の定義では [math]n = 1[/math] のとき [math]S_1 = 1[/math] ですが、条件をより簡潔にするため、[math]n = 0[/math] のときに [math]S_0 = 0[/math] を返すようにしています(このため、再帰呼び出しの回数が1回多くなります)。 条件演算子を用いたプログラム2のほうがコンパクトですが、理解しにくいならプログラム1だけわかれば問題ありません。 **演習1 [#j9a31cd5] プログラム1またはプログラム2を作成し、実行結果を確認せよ。 *再帰呼び出しの振る舞い [#daaa814e] 再帰呼び出しの振る舞いを見るために、printf関数を呼び出してみましょう(プログラム3)。 #geshi(c){{ int sum(int n) { printf(">> sum(%d) が呼び出されました\n", n); if (n == 1) { return 1; } else { return sum(n - 1) + n; } } }} このプログラムを実行すると、次のようになります。 #geshi(sh){{ luna% a.out >> sum(5) が呼び出されました >> sum(4) が呼び出されました >> sum(3) が呼び出されました >> sum(2) が呼び出されました >> sum(1) が呼び出されました 15 }} まず、main関数が sum(5) を呼び出します。 次に、sum(5) は、n が 1 より大きいので、sum(4) を呼び出します(再帰呼び出し)。 sum(4) も、n が 1 より大きいので、 sum(3) を呼び出します。 同様にして、sum(3) が sum(2) を、sum(2) が sum(1) を呼び出します。 sum(1) は、n が 1 より大きくないので、(再帰呼び出しを行わずに)1 を sum(2) に返します。 sum(2) は、sum(1) から 1 を受け取り、1 + 2 を計算して sum(3) に返します。 sum(3) は、sum(2) から 3 を受け取り、3 + 3 を計算して sum(4) に返します。 sum(4) は、sum(3) から 6 を受け取り、6 + 4 を計算して sum(5) に返します。 sum(5) は、sum(4) から 10 を受け取り、10 + 5 を計算してmain関数に返します。 このようにして、main関数が sum(5) から 15 を受け取るまでの間に、sum関数が何度も再帰的に呼び出されています。 **演習2 [#d0606317] プログラム1またはプログラム2をプログラム3のように変更し、実行結果を確認せよ。 *注意すべきこと [#v4baa89d] **再帰呼び出しが停止するように書く [#a7fe3f77] まず、再帰呼び出しを行う関数は、再帰呼び出しが必ず停止するように書かなければなりません。 よくありがちな間違いとして、[math]n = 1[/math] のときの処理を忘れてしまうことがあります(プログラム4)。 #geshi(c){{ int sum(int n) {{ printf(">> sum(%d) が呼び出されました\n", n); return sum(n - 1) + n; } }} すると、sum(5) を呼び出すと、sum(1) が sum(0) を、sum(0) が sum(−1) を呼び出すので、sum関数が延々と呼び出されて停止せず、無限ループに陥ります。 実際には、関数が呼び出されるたびに、メモリーのスタック領域を消費しますので、''スタック領域がオーバーフロー''して''セグメント・エラー''が発生します。 スタック・オーバーフローについては、計算機アーキテクチャーの授業できちんと勉強してください。 したがって、再帰呼び出しを行う関数は、再帰呼び出しが停止するように書かなければなりません。 とくに、条件分岐がない再帰呼び出しはあり得ません。 **再帰呼び出しが停止するように呼び出す [#c42dc5fb] sum関数が、プログラム1のように正しく定義されていたとしても、sum(−5) を呼び出すと、sum関数が延々と呼び出されて停止せず、無限ループに陥り、スタック・オーバーフローが発生します。 したがって、再帰呼び出しを行う関数を呼び出すときは、再帰呼び出しが停止するように呼び出さなければなりません。 **なるべく再帰呼び出しを使わない [#u8e25cb3] 再帰呼び出しはメモリーのスタック領域を消費します。 また、何度も関数呼び出しを行うので、実行に時間がかかります。 再帰呼び出しを行わなくても良い場合には、再帰呼び出しを使うべきではありません。 もちろん、1からnまでの整数の合計も、再帰呼び出しを使わなくても計算できます(プログラム5, 6)。 #geshi(c){{ /* * for文を使って1からnまでの整数の合計を求める */ int sum(int n) { int i, s = 0; for (i = 1; i <= n; i++) { s += i; } return s; } }} #geshi(c){{ /* * 公式を使って1からnまでの整数の合計を求める */ int sum(int n) { return n * (n + 1) / 2; } }} **演習3 [#dc80d544] プログラム3をプログラム4のように変更し、実行結果を確認せよ。 *再帰呼び出しを使ったプログラムの例 [#x9717b86] **階乗 [#v279355b] 再帰呼び出しを使うと簡単に定義できる関数の代表例が階乗です。 \[ \begin{align} n! &= n \times (n - 1) \times \dots \times 2 \times 1 \\ &= n \times (n - 1)! \end{align} \] ただし、[math]0! = 1[/math]です。 #geshi(c){{ int fact(int n) { return n == 0 ? 1 : n * fact(n - 1); } }} if文で書くと次のようになります。 #geshi(c){{ int fact(int n) { if (n == 0) { return 1; } else { return n * fact(n - 1); } } }} 階乗を求める関数は、再帰呼び出しを使わなくても定義できます。 #geshi(c){{ int fact(int n) { int i, f = 1; for (i = n; i > 1; i--) { f *= i; } return f; } }} **階段の昇り方 [#qe4a77a5] 次のような問題を考えてみましょう。 階段を1段ずつか1段飛ばしで昇るとき、全部で20段ある階段の昇り方は何通りか この問題は、再帰的に考えると、簡単に解けます。 最後の昇り方だけを考えると、最後は、19段目から1段昇るか、18段目から1段飛ばしで昇るかのいずれかです。 つまり、20段目までの昇り方が何通りあるかは、19段目までの昇り方が何通りあるかと18段目までの昇り方が何通りあるかがわかれば、この二つの和によって求めることができます。 これを一般的に書くと、n段目に昇る方法は、n−1段目から1段昇るか、n−2段目から1段飛ばしで昇るかのいずれかであり、n段目までの昇り方の場合の数、n−1段目までとn−2段目までの昇り方の場合の数の和で求まります。 ただし、1段目までの昇り方は1通り、2段目までの昇り方は(1段ずつ2段昇る方法と1段飛ばしで昇る方法の)2通りです。 したがって、n段目までの昇り方の場合の数を [math]S_n[/math] とすると、[math]S_n = S_{n-1} + S_{n-2}[/math] となります。 ただし、[math]S_1 = 1[/math], [math]S_2 = 2[/math] です。 #geshi(c){{ /* * n段目までの階段を1段ずつか1段飛ばしで昇る方法の場合の数を求める */ int step(int n) { switch (n) { case 1: return 1; case 2: return 2; default: return step(n - 1) + step(n - 2); } } }} ---- *まとめ [#kdfa9db0] 再帰呼び出しは、関数の中でその関数自身を呼び出すことです。 最も高速なソート(並べ替え)アルゴリズムであるクイック・ソートは、分割統治法による再帰的アルゴリズムであり、再帰呼び出しを使って実装されます。 (分割統治法とクイック・ソートについては、データ構造とアルゴリズムやプログラム演習の授業できちんと勉強してください。) 再帰呼び出しでは、必ず、再帰呼び出しが停止するように再帰関数を定義し、再帰呼び出しが停止するように再帰関数を呼び出す必要があります。 また、再帰呼び出しは呼び出すたびにメモリーのスタック領域を消費するので、再帰呼び出しを行う必要がないときに使わないように注意しましょう。 ---- *練習問題 [#c0a763c2] 練習問題は[[こちら>授業/C言語基礎/再帰呼び出し/練習問題]]。
タイムスタンプを変更しない
ある関数の中でその関数自身を呼び出すことを''再帰呼び出し''といいます。 再帰呼び出しを用いると簡潔なプログラムにできる場合がありますが、再帰呼び出しには注意しなければならないこともあります。 ここでは、再帰呼び出しについて説明します。 *再帰的定義 [#ne8f32b9] [math]1[/math] から [math]n[/math] までの整数の和 [math]S_n[/math] について考えてみます。 \[ S_n = 1 + 2 + 3 + \dots + (n - 1) + n \] [math]S_n[/math] は、[math]1[/math] から [math]n-1[/math] までの整数の和 [math]S_{n-1}[/math] に [math]n[/math] を加えたものと考えることができます。 したがって、[math]S_n[/math] は、[math]S_{n-1}[/math] を使って次のように定義できます。 \[ \begin{align} S_n &= \left( 1 + 2 + 3 + \dots + (n - 1) \right) + n \\ &= S_{n-1} + n \end{align} \] このような定義を''再帰的定義''といいます。 ただし、[math]n = 1[/math]のときは [math]S_1 = 1[/math] です。 再帰的に定義された関数を''再帰関数''といい、再帰関数が関数の中で自分自身を呼び出すことを''再帰呼び出し''といいます。 整数の和を求めるプログラムを再帰呼び出しを使って書くと、次のようになります(プログラム1)。 #geshi(c){{ /* * 1からnまでの整数の合計を求める(再帰関数) */ int sum(int n) { if (n == 1) { return 1; } else { return sum(n - 1) + n; // 再帰呼び出し } } int main(void) { int i = sum(5); printf("%d\n", i); return 0; } }} 関数sumは、条件演算子を使って次のようにも書けます(プログラム2)。 #geshi(c){{ int sum(int n) { return n ? sum(n - 1) + n : 0; } }} n が 0 でないときは条件を満たすとして sum(n - 1) + n を計算して返します。 そうでないときは 0 を返します。 元の定義では [math]n = 1[/math] のとき [math]S_1 = 1[/math] ですが、条件をより簡潔にするため、[math]n = 0[/math] のときに [math]S_0 = 0[/math] を返すようにしています(このため、再帰呼び出しの回数が1回多くなります)。 条件演算子を用いたプログラム2のほうがコンパクトですが、理解しにくいならプログラム1だけわかれば問題ありません。 **演習1 [#j9a31cd5] プログラム1またはプログラム2を作成し、実行結果を確認せよ。 *再帰呼び出しの振る舞い [#daaa814e] 再帰呼び出しの振る舞いを見るために、printf関数を呼び出してみましょう(プログラム3)。 #geshi(c){{ int sum(int n) { printf(">> sum(%d) が呼び出されました\n", n); if (n == 1) { return 1; } else { return sum(n - 1) + n; } } }} このプログラムを実行すると、次のようになります。 #geshi(sh){{ luna% a.out >> sum(5) が呼び出されました >> sum(4) が呼び出されました >> sum(3) が呼び出されました >> sum(2) が呼び出されました >> sum(1) が呼び出されました 15 }} まず、main関数が sum(5) を呼び出します。 次に、sum(5) は、n が 1 より大きいので、sum(4) を呼び出します(再帰呼び出し)。 sum(4) も、n が 1 より大きいので、 sum(3) を呼び出します。 同様にして、sum(3) が sum(2) を、sum(2) が sum(1) を呼び出します。 sum(1) は、n が 1 より大きくないので、(再帰呼び出しを行わずに)1 を sum(2) に返します。 sum(2) は、sum(1) から 1 を受け取り、1 + 2 を計算して sum(3) に返します。 sum(3) は、sum(2) から 3 を受け取り、3 + 3 を計算して sum(4) に返します。 sum(4) は、sum(3) から 6 を受け取り、6 + 4 を計算して sum(5) に返します。 sum(5) は、sum(4) から 10 を受け取り、10 + 5 を計算してmain関数に返します。 このようにして、main関数が sum(5) から 15 を受け取るまでの間に、sum関数が何度も再帰的に呼び出されています。 **演習2 [#d0606317] プログラム1またはプログラム2をプログラム3のように変更し、実行結果を確認せよ。 *注意すべきこと [#v4baa89d] **再帰呼び出しが停止するように書く [#a7fe3f77] まず、再帰呼び出しを行う関数は、再帰呼び出しが必ず停止するように書かなければなりません。 よくありがちな間違いとして、[math]n = 1[/math] のときの処理を忘れてしまうことがあります(プログラム4)。 #geshi(c){{ int sum(int n) {{ printf(">> sum(%d) が呼び出されました\n", n); return sum(n - 1) + n; } }} すると、sum(5) を呼び出すと、sum(1) が sum(0) を、sum(0) が sum(−1) を呼び出すので、sum関数が延々と呼び出されて停止せず、無限ループに陥ります。 実際には、関数が呼び出されるたびに、メモリーのスタック領域を消費しますので、''スタック領域がオーバーフロー''して''セグメント・エラー''が発生します。 スタック・オーバーフローについては、計算機アーキテクチャーの授業できちんと勉強してください。 したがって、再帰呼び出しを行う関数は、再帰呼び出しが停止するように書かなければなりません。 とくに、条件分岐がない再帰呼び出しはあり得ません。 **再帰呼び出しが停止するように呼び出す [#c42dc5fb] sum関数が、プログラム1のように正しく定義されていたとしても、sum(−5) を呼び出すと、sum関数が延々と呼び出されて停止せず、無限ループに陥り、スタック・オーバーフローが発生します。 したがって、再帰呼び出しを行う関数を呼び出すときは、再帰呼び出しが停止するように呼び出さなければなりません。 **なるべく再帰呼び出しを使わない [#u8e25cb3] 再帰呼び出しはメモリーのスタック領域を消費します。 また、何度も関数呼び出しを行うので、実行に時間がかかります。 再帰呼び出しを行わなくても良い場合には、再帰呼び出しを使うべきではありません。 もちろん、1からnまでの整数の合計も、再帰呼び出しを使わなくても計算できます(プログラム5, 6)。 #geshi(c){{ /* * for文を使って1からnまでの整数の合計を求める */ int sum(int n) { int i, s = 0; for (i = 1; i <= n; i++) { s += i; } return s; } }} #geshi(c){{ /* * 公式を使って1からnまでの整数の合計を求める */ int sum(int n) { return n * (n + 1) / 2; } }} **演習3 [#dc80d544] プログラム3をプログラム4のように変更し、実行結果を確認せよ。 *再帰呼び出しを使ったプログラムの例 [#x9717b86] **階乗 [#v279355b] 再帰呼び出しを使うと簡単に定義できる関数の代表例が階乗です。 \[ \begin{align} n! &= n \times (n - 1) \times \dots \times 2 \times 1 \\ &= n \times (n - 1)! \end{align} \] ただし、[math]0! = 1[/math]です。 #geshi(c){{ int fact(int n) { return n == 0 ? 1 : n * fact(n - 1); } }} if文で書くと次のようになります。 #geshi(c){{ int fact(int n) { if (n == 0) { return 1; } else { return n * fact(n - 1); } } }} 階乗を求める関数は、再帰呼び出しを使わなくても定義できます。 #geshi(c){{ int fact(int n) { int i, f = 1; for (i = n; i > 1; i--) { f *= i; } return f; } }} **階段の昇り方 [#qe4a77a5] 次のような問題を考えてみましょう。 階段を1段ずつか1段飛ばしで昇るとき、全部で20段ある階段の昇り方は何通りか この問題は、再帰的に考えると、簡単に解けます。 最後の昇り方だけを考えると、最後は、19段目から1段昇るか、18段目から1段飛ばしで昇るかのいずれかです。 つまり、20段目までの昇り方が何通りあるかは、19段目までの昇り方が何通りあるかと18段目までの昇り方が何通りあるかがわかれば、この二つの和によって求めることができます。 これを一般的に書くと、n段目に昇る方法は、n−1段目から1段昇るか、n−2段目から1段飛ばしで昇るかのいずれかであり、n段目までの昇り方の場合の数、n−1段目までとn−2段目までの昇り方の場合の数の和で求まります。 ただし、1段目までの昇り方は1通り、2段目までの昇り方は(1段ずつ2段昇る方法と1段飛ばしで昇る方法の)2通りです。 したがって、n段目までの昇り方の場合の数を [math]S_n[/math] とすると、[math]S_n = S_{n-1} + S_{n-2}[/math] となります。 ただし、[math]S_1 = 1[/math], [math]S_2 = 2[/math] です。 #geshi(c){{ /* * n段目までの階段を1段ずつか1段飛ばしで昇る方法の場合の数を求める */ int step(int n) { switch (n) { case 1: return 1; case 2: return 2; default: return step(n - 1) + step(n - 2); } } }} ---- *まとめ [#kdfa9db0] 再帰呼び出しは、関数の中でその関数自身を呼び出すことです。 最も高速なソート(並べ替え)アルゴリズムであるクイック・ソートは、分割統治法による再帰的アルゴリズムであり、再帰呼び出しを使って実装されます。 (分割統治法とクイック・ソートについては、データ構造とアルゴリズムやプログラム演習の授業できちんと勉強してください。) 再帰呼び出しでは、必ず、再帰呼び出しが停止するように再帰関数を定義し、再帰呼び出しが停止するように再帰関数を呼び出す必要があります。 また、再帰呼び出しは呼び出すたびにメモリーのスタック領域を消費するので、再帰呼び出しを行う必要がないときに使わないように注意しましょう。 ---- *練習問題 [#c0a763c2] 練習問題は[[こちら>授業/C言語基礎/再帰呼び出し/練習問題]]。
テキスト整形のルールを表示する