1. ホーム
  2. function

[解決済み] 再帰的関数の仕組みを理解する

2022-09-11 04:51:21

質問

タイトルにあるように、私は非常に基本的なプログラミングの質問があるのですが、まだ理解することができません。 さまざまなオンライン スレッドから、すべての (非常に巧妙な) "In order to understand recursion, you must first understand recursion." の返信をフィルタリングしても、まだよく理解できていません。

知らないことを知らないことに直面すると、間違った質問をしたり、正しい質問をしたりする傾向があることを理解し、同じような見通しを持つ誰かが、私の再帰的な電球を点灯させるのに役立つ知識の一部を共有できることを期待して、私の質問が何を考えているのかを共有します!

ここに関数があります(構文はSwiftで書かれています)。

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

2と5を引数にします。

println(sumInts(a: 2, b: 5))

明らかに答えは14です。 しかし、その値がどのように達成されるのかが明確ではありません。

これが私の2つの難点です。

  1. この関数は、ある条件を満たすまで再帰的に呼び出されます。 その条件は a > b で、この条件を満たしたときに 0 を返します。 一見、戻り値が0になると思ってしまいますが、これは明らかに不正解です。

  2. 各反復で 'a' の値をプリントアウトすると、2、3、4、5 (この時点で 5+1 > b という最初の条件を満たす) という期待通りの値が得られますが、14 という値がどのように達成されるかはまだわかりません。

私の最初の考えは、次のようなことが魔法のように起こっているということです。

var answer = a;
answer += a+1 until a > b;
return answer;   

というわけで、魔法を除外すると、何か得られないんです。 暗黙の了解ではなく、何が起こっているのか理解したいです。

誰かが親切にこの種の関数の間に技術的に何が起こって、なぜ結果が0でないのか、そしてどのように、最終的に説明することができれば。 a + sumInts(a: a + 1, b: b) = 14 になるのか、説明していただけると幸いです。

どのように解決するのですか?

I を考える は、同じ関数が何度も呼び出されると考えているために混乱しているのだと思います。もし、同じ関数が何度も呼び出されることだと考えれば、それはより明確かもしれません。

0 を返す関数のコピーは 1 つだけで、それは最初のものではありません (最後のものです)。ですから、最初のものを呼び出した結果は0ではありません。

2つ目の混乱については、再帰を英語で綴った方が分かりやすいと思います。この行を読んでみてください。

return a + sumInts(a + 1, b: b)

として、"関数のコピーの'a'の値に(...を加えた値を返す、関数の別のコピーの戻り値で、2番目のコピーの'a'の値に(... "を加えた値である。関数のそれぞれのコピーはa >の条件が満たされるまで、1ずつ増やした自身の新しいコピーを産み出します。

a > b の条件が真になるまでに、関数のコピーの (潜在的に任意の) 長いスタックをすべて実行中に持ち、すべて次のコピーの結果を待って、何を 'a' に追加すべきかを探しています。

(編集: また、注意すべきことは、私が言及した関数のコピーのスタックは実際のメモリを消費し、それが大きくなりすぎるとプログラムがクラッシュするということです。コンパイラーは場合によってはそれを最適化できますが、スタック空間を使い果たすことは、多くの言語における再帰的関数の重要かつ不運な制限です)