再帰とは
さいき
関数が処理の中で自分自身を呼び出すこと。問題を同じ形の小さな問題に分けて解き、それ以上分けない場合(基底)で呼び出しを終える。呼び出しごとにスタックを使うので深すぎるとあふれる。最後に自分を呼ぶだけの末尾再帰は、ループに変換できる。
「再帰」は、8分野の14問の練習問題に出てきます(データ構造とアルゴリズム, リンカ・ローダと実行形式, プログラミングの基礎(擬似言語のトレース)など)。
この用語の分野: データ構造とアルゴリズム
再帰の練習問題に挑戦
RISC-Vで、自分自身を呼び出す再帰関数を書くときに、raをスタックに保存し忘れるとどうなるか。
- A内側の呼び出しでraが上書きされ、外側の関数が正しい呼び出し元へ戻れなくなる
- BCPUが自動でraを保存するので、何も問題は起きない
- C再帰の深さに関係なく、計算結果が2倍になる
再帰が深くなりすぎてスタックの上限を超えたとき、Linuxなどで一般に起こることとして正しいものはどれか。
- Aスタックの先にある、アクセスを禁止したガードページに触れて、プログラムが異常終了する
- BOSが自動でスタックをディスクに移し、いくらでも深く再帰できる
- C古いスタックフレームが自動で消され、計算は正しく続く
解説の中の「再帰」
再帰呼び出しのjalは、raを「自分の中の呼び出しの次の命令」で上書きします。
RISC-Vで、自分自身を呼び出す再帰関数を書くときに、raをスタックに保存し忘れるとどうなるか。この関数の再帰呼び出しは、関数の最後の処理で、その結果をそのまま返しています(末尾呼び出し)。
上の関数の最後の再帰呼び出しに末尾呼び出しの最適化を行うと、どのような効果があるか。再帰が深すぎてスタックがここに達すると、ページフォルトが起きてOSがプログラムを止めます(セグメンテーション違反)。
再帰が深くなりすぎてスタックの上限を超えたとき、Linuxなどで一般に起こることとして正しいものはどれか。スタックは後から入れたものを先に取り出す(LIFO)構造で、呼び出しが入れ子や再帰になっても正しい順で戻れます。
プログラムでサブルーチン(関数)を呼び出すとき、戻り先のアドレスなどを一時的に保存するために一般的に使われる領域はどれ…そのため、再帰で同じ関数が何重に呼ばれても、それぞれが別の変数を持てます。
C言語の関数の中で宣言した、staticの付かない局所変数(自動変数)は、実行中どこに置かれるか。
「再帰」が出てくる問題(14問)
- RISC-Vで、自分自身を呼び出す再帰関数を書くときに、raをスタックに保存し忘れるとどうなるか。
- 上の関数の最後の再帰呼び出しに末尾呼び出しの最適化を行うと、どのような効果があるか。
- 再帰が深くなりすぎてスタックの上限を超えたとき、Linuxなどで一般に起こることとして正しいものはどれか。
- 辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。頂点 A から再帰的な深さ優先探索を行う。隣の頂点はここに書いた順に調べ、まだ訪れていない頂点が見つかったらすぐにその頂点へ進む。頂点を訪れる順はどれか。
- フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fib(n−2) を返す」と再帰で定義した。fib(5) を呼んだとき、fib が呼ばれる回数は最初の呼び出しを含めて何回か。
- プログラムでサブルーチン(関数)を呼び出すとき、戻り先のアドレスなどを一時的に保存するために一般的に使われる領域はどれか。
- C言語の関数の中で宣言した、staticの付かない局所変数(自動変数)は、実行中どこに置かれるか。
- プロセスのヒープとスタックを、間に広い空きをはさんで反対向きに伸ばす配置にする利点として正しいものはどれか。
- MMUを持たない小さなマイコンで、スタックの使いすぎについて注意すべきこととして正しいものはどれか。
- 辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組はどれか。
- 関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f(84, 36) を呼んだときの戻り値と、f が呼ばれる回数(最初の呼び出しを含む)の組はどれか。
- ÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 pow を pow(2, 10) として呼び出したとき、pow が呼ばれる回数(最初の呼出しを含む)はどれか。
- 次の関数 fib を fib(10) として呼び出したときの戻り値はどれか。
- int は32ビット(最大値 2147483647)とする。上の関数 fact(n) が、n の階乗をオーバーフローを起こさずに正しく返す最大の n はどれか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。