🧑🏿 🕴🏼 🥘 再帰。面白いパズル 🧑🏻‍🤝‍🧑🏻 🍠 🍿

こんにちは、Habrahabr！

この記事では、再帰の問題とその解決方法に焦点を当てます。

再帰の概要

再帰はかなり一般的な現象であり、科学の分野だけでなく、日常生活でも発生します。たとえば、Drosteエフェクト、Sierpinskiの三角形など。再帰を表示するオプションの1つは、もちろん、電源をオンにした後、コンピューターのモニター画面にWebカメラを向けることです。したがって、カメラはコンピューター画面の画像を記録し、この画面に表示すると、閉ループのようなものが得られます。その結果、トンネルに似たものを観察します。

プログラミングでは、再帰は関数と密接に関連しています。より正確には、プログラミングの関数のおかげで、再帰や再帰関数などがあります。簡単な言葉で言えば、再帰とは、それ自体を通る関数（メソッド）の一部の定義です。つまり、直接（本体で）または間接的に（別の関数を介して）呼び出す関数です。

再帰については多くのことが言われています。良いリソースをいくつか紹介します

読者は理論的には再帰に精通しており、それが何であるかを知っていると想定されています。この記事では、再帰の問題にさらに注意を払います。

タスク

再帰の研究において、再帰を理解する最も効果的な方法は問題を解決することです。

再帰の問題を解決するには？

まず、再帰は一種のバストであることを理解する必要があります。一般的に、反復的に解決されるすべてのものは再帰的に、つまり再帰関数を使用して解決できます。

ネットワークから

再帰形式で実装されたアルゴリズムは、反復形式で書き換えることができ、その逆も可能です。これが必要かどうか、そしてそれがどれほど効果的であるかという疑問が残っています。

正当化するために、そのような議論をもたらすことができます。

まず、再帰と反復の定義を思い出してください。再帰は、プログラムがそれ自体を直接呼び出す、または他のプログラムを使用してデータ処理を編成する方法です。反復とは、再帰的なプログラム呼び出しにつながることなく、特定のアクションを何度も繰り返すデータ処理を編成する方法です。

それから、それらは相互に交換可能であると結論付けることができますが、リソースと速度の点で常に同じコストではありません。正当化するために、例を挙げることができます。特定のアルゴリズムを編成するために、カウンターの現在の値に応じて一連のアクションを実行するサイクルがあります（依存しない場合があります）。サイクルがあると、身体が一連のアクションを繰り返すことを意味します-サイクルの反復。操作を別のサブルーチンに転送し、カウンター値がある場合はそれに渡すことができます。サブルーチンが完了すると、サイクルの実行条件をチェックし、trueの場合はサブルーチンの新しい呼び出しに進み、falseの場合は実行を完了します。なぜならループの内容全体をサブルーチンに入れます。つまり、ループの実行条件もサブルーチンに置かれ、関数の戻り値、参照によって渡されるパラメーター、サブルーチンへのポインター、グローバル変数を通じて取得できます。さらに、サイクルから特定のサブプログラムへの呼び出しは、任意の条件（以前はループ状態にあったもの）によって導かれ、サブプログラム自体からの呼び出し（値を返す、または単にシャットダウンする）ではなく、呼び出しに変換するのが簡単であることを示すのは簡単です。さて、抽象プログラムを見ると、サブルーチンに値を渡し、それらを使用しているように見えます。これにより、完了時にサブルーチンが変更されます。このアルゴリズムを解決するために、反復ループを再帰的なサブルーチン呼び出しに置き換えました。

再帰を反復アプローチに減らすタスクは対称的です。

要約すると、次の考えを表現できます。各アプローチには、特定のタスクの特定の要件によって決定されるタスクのクラスがあります。

詳細については、こちらをご覧ください。

列挙（ループ）と同様に、再帰には停止条件（基本ケース）が必要です（そうでない場合、再帰ループのように、永久に動作します-無限）。この条件は、再帰が行われるケースです（再帰ステップ）。各ステップで、次の条件が基本条件をトリガーし、再帰が停止する（つまり、最後の関数呼び出しに戻る）まで、再帰関数が呼び出されます。ソリューション全体が基本ケースを解決することになります。複雑な問題を解決するために再帰関数が呼び出される場合（ベースケースではありません）、問題をより単純なものに減らすために、多くの再帰呼び出しまたはステップが実行されます。基本的な解決策が得られるまで続きます。

したがって、再帰関数は

停止条件またはベースケース
継続条件または再帰ステップは、タスクをより単純なものに減らす方法です。

階乗を見ることでこれを考慮してください：

public class Solution { public static int recursion(int n) { //   //   //     ? if (n == 1) { return 1; } //   /   return recursion(n - 1) * n; } public static void main(String[] args) { System.out.println(recursion(5)); //    } }

ここで、基本条件はn = 1のときの条件です。 1！= 1であることがわかっているため、1！何も必要ありません。 2を計算するには！ 1を使用できます、つまり 2！= 1！* 2。 3を計算するには！ 2が必要です！* 3 ... nを計算するには！（n-1）が必要です！* n。これは再帰ステップです。つまり、数値nから階乗値を取得するには、前の数値から階乗値をn倍すれば十分です。

再帰を説明するとき、ネットワークはフィボナッチ数とハノイの塔を見つける問題も与えます

次に、さまざまなレベルの複雑さを持つタスクを検討します。

上記の方法を使用して自分で解決してください。決めるとき、再帰的に考えてみてください。問題の基本的なケースは何ですか？再帰ステップまたは再帰条件とは何ですか？

行こう！ソリューションはJava言語で提供されます。

A：1からn

自然数nを指定します。 1からnまでのすべての数値を印刷します。

解決策

 public class Solution { public static String recursion(int n) { //   if (n == 1) { return "1"; } //   /   return recursion(n - 1) + " " + n; } public static void main(String[] args) { System.out.println(recursion(10)); //    } }

B：AからB

2つの整数AとBが与えられた場合（それぞれ別々の行に）。 AからBまでのすべての数値を、A <Bの場合は昇順で、それ以外の場合は降順で印刷します。

解決策

 public class Solution { public static String recursion(int a, int b) { //    if (a > b) { //   if (a == b) { return Integer.toString(a); } //   /   return a + " " + recursion(a - 1, b); } else { //   if (a == b) { return Integer.toString(a); } //   /   return a + " " + recursion(a + 1, b); } } public static void main(String[] args) { System.out.println(recursion(20, 15)); //    System.out.println(recursion(10, 15)); //    } }

C：アッカーマン関数

計算可能性の理論では、次のように定義されたアッカーマン関数A（m、n）が重要な役割を果たします。

それぞれが別々の行にある、2つの非負の整数mおよびnを指定します。 A（m、n）を印刷します。

解決策

 public class Solution { public static int recursion(int m, int n) { //   if (m == 0) { return n + 1; } //   /   else if (n == 0 && m > 0) { return recursion(m - 1, 1); } //   /   else { return recursion(m - 1, recursion(m, n - 1)); } } public static void main(String[] args) { System.out.println(recursion(3, 2)); //    } }

D：正確なデュース

自然数Nを指定します。数値Nが2の正確なべき乗である場合はYESを、そうでない場合はNOを出力します。

累乗の操作は使用できません！

解決策

 public class Solution { public static int recursion(double n) { //   if (n == 1) { return 1; } //   else if (n > 1 && n < 2) { return 0; } //   /   else { return recursion(n / 2); } } public static void main(String[] args) { double n = 64; //    if (recursion(n) == 1) { System.out.println("Yes"); } else { System.out.println("No"); } } }

E：数字の合計

自然数Nを指定します。その桁の合計を計算します。

この問題を解決するとき、文字列、リスト、配列を使用することはできません（もちろん、ループ）。

解決策

 public class Solution { public static int recursion(int n) { //   if (n < 10) { return n; }//   /   else { return n % 10 + recursion(n / 10); } } public static void main(String[] args) { System.out.println(recursion(123)); //    } }

F：右から左への数字

自然数Nを指定します。すべての数字を1つずつ逆順に印刷し、スペースまたは改行で区切ります。

この問題を解決するとき、文字列、リスト、配列を使用することはできません（もちろん、ループ）。再帰と整数演算のみが許可されています。

解決策

 public class Solution { public static int recursion(int n) { //   if (n < 10) { return n; }//   /   else { System.out.print(n % 10 + " "); return recursion(n / 10); } } public static void main(String[] args) { System.out.println(recursion(123)); //    } }

G：左から右への数字の数

自然数Nを指定します。通常の順序ですべての数字を1つずつ出力し、スペースまたは改行で区切ります。

この問題を解決するとき、文字列、リスト、配列を使用することはできません（もちろん、ループ）。再帰と整数演算のみが許可されています。

解決策

 public class Solution { public static String recursion(int n) { //   if (n < 10) { return Integer.toString(n); } //   /   else { return recursion(n / 10) + " " + n % 10; } } public static void main(String[] args) { System.out.println(recursion(153)); //    } }

H：単純性の確認

自然数n> 1が与えられた場合。簡単かどうか確認してください。プログラムは、数値が素数の場合はYESを、数値が複合の場合はNOを印刷する必要があります。アルゴリズムにはO（logn）の複雑さが必要です。

適応症タスク自体が再帰的ではないことは明らかです。なぜなら、単純化のために数値nをチェックすることは、より小さい数値の単純性をチェックすることに要約されません。したがって、別の再帰パラメーター（数値の除数）を作成する必要があります。このパラメーターによって正確に再帰が実行されます。

解決策

 public class Solution { public static boolean recursion(int n, int i) { // i-  .      2 //   if (n < 2) { return false; } //   else if (n == 2) { return true; } //   else if (n % i == 0) { return false; } //   /   else if (i < n / 2) { return recursion(n, i + 1); } else { return true; } } public static void main(String[] args) { System.out.println(recursion(18, 2)); //    } }

I：因数分解

自然数n> 1が与えられた場合。多重度を考慮して、この数のすべての素因数を減少しない順で出力します。アルゴリズムにはO（logn）の複雑さが必要です。

解決策

 public class Solution { public static void recursion(int n, int k) { // k-  .      2 //   if (k > n / 2) { System.out.println(n); return; } //   /   if (n % k == 0) { System.out.println(k); recursion(n / k, k); } //   /   else { recursion(n, ++k); } } public static void main(String[] args) { recursion(150, 2); //    } }

J：パリンドローム

小文字のラテン文字のみで構成される単語を考えます。この単語が回文であるかどうかを確認します。 YESまたはNOを印刷します。

この問題を解決する場合、サイクルを使用できません。Pythonソリューションでは、1以外のステップでスライスを使用できません。

解決策

 public class Solution { public static String recursion(String s) { //   if (s.length() == 1) { return "YES"; } else { if (s.substring(0, 1).equals(s.substring(s.length() - 1, s.length()))) { //   if (s.length() == 2) { return "YES"; } //   /   return recursion(s.substring(1, s.length() - 1)); } else { return "NO"; } } } public static void main(String[] args) { System.out.println(recursion("radar")); //    } }

別の解決策

 public class Solution { public static boolean recursion(String s) { char firstChar; char lastChar; int size = s.length(); String subString; //   if (size <= 1) { return true; } else { firstChar = s.toCharArray()[0]; lastChar = s.toCharArray()[size - 1]; subString = s.substring(1, size - 1); //   /   return firstChar == lastChar && recursion(subString); } } public static void main(String[] args) { //    if (recursion("radar")) { System.out.println("YES"); } else { System.out.println("NO"); } } }

K：奇数のシーケンス番号を出力します

自然数のシーケンス（行ごとに1つの数字）が与えられ、数字の0で終了します。順序を維持しながら、このシーケンスからすべての奇数を出力します。

このタスクでは、グローバル変数を使用して、再帰関数にパラメーターを渡すことはできません。この関数は、キーボードからデータを読み取ることでデータを受け取ります。この関数は値を返しませんが、すぐに結果を画面に表示します。メインプログラムは、この関数の呼び出しのみで構成する必要があります。

解決策

 public class Solution { public static void recursion() { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); //   if (n > 0) { //   /   if (n % 2 == 1) { System.out.println(n); recursion(); } else { recursion(); } } } public static void main(String[] args) { recursion(); //    } }

L：シーケンスメンバーを奇数で出力します

自然数のシーケンス（行ごとに1つの数字）が与えられ、数字の0で終わる場合。最初、3番目、5番目などを出力します。入力された番号から。末尾のゼロは必要ありません。

このタスクでは、グローバル変数を使用して、再帰関数にパラメーターを渡すことはできません。この関数は、キーボードからデータを読み取ることでデータを受け取ります。この関数は値を返しませんが、すぐに結果を画面に表示します。メインプログラムは、この関数の呼び出しのみで構成する必要があります。

解決策

 public class Solution { public static void recursion() { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); //   if (n > 0) { int m = in.nextInt(); System.out.println(n); //   if (m > 0) { //   /   recursion(); } } } public static void main(String[] args) { recursion(); //    } }

M：最大シーケンス

0で終わる自然数のシーケンス（行ごとに1つの番号）を指定します。このシーケンスの番号の最大値を決定します。

このタスクでは、グローバル変数を使用して、再帰関数にパラメーターを渡すことはできません。この関数は、キーボードからデータを読み取ることでデータを受け取ります。この関数は単一の値を返します：読み取られたシーケンスの最大値。シーケンスに少なくとも1つの数値（ゼロを除く）が含まれていることが保証されます。

解決策

 public class Solution { public static int recursion() { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); //   if (n == 0) { return 0; } //   /   else { return Math.max(n, recursion()); } } public static void main(String[] args) { System.out.println(recursion()); //    } }

N：シーケンスの平均値

自然数のシーケンス（行ごとに1つの数字）が与えられ、数字の0で終了します。このシーケンスの要素の平均値を決定します（最後のゼロを除く）。

このタスクではグローバル変数を使用できません。この関数は、データをパラメーターとして受け取るのではなく、キーボードから読み取ることでデータを受け取ります。 Pythonプログラムでは、関数は数字のペアのタプルを返します。つまり、シーケンス内の要素の数とその合計です。 C ++プログラムでは、結果は2つの変数に書き込まれ、参照によって関数に渡されます。

シーケンスに少なくとも1つの数値（ゼロを除く）が含まれていることが保証されます。

解決策

 public class Solution { public static void recursion(int sum, int count) { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); //   if (n > 0) { //   /   recursion(sum + n, ++count); } else if (sum > 0 && count > 0) { System.out.println((float) sum / count); } } public static void main(String[] args) { recursion(0, 0); //    } }

O：2番目に高い

番号0で終わる自然数のシーケンス（1行に1つの番号）が与えられます。このシーケンスの2番目に大きい要素の値、つまり、シーケンスから最大の要素が削除された場合に最大になる要素の値を決定します。

このタスクではグローバル変数を使用できません。この関数は、データをパラメーターとして受け取るのではなく、キーボードから読み取ることでデータを受け取ります。 Pythonプログラムでは、関数は複数の数値のタプルの形式で結果を返しますが、関数はパラメーターをまったく受け取りません。 C ++プログラムでは、結果は変数に書き込まれ、参照によって関数に渡されます。関数は、値を返すために使用されるパラメーター以外のパラメーターを受け取りません。

シーケンスに少なくとも2つの数字（ゼロを除く）が含まれていることが保証されます。

解決策

 public class Solution { public static void recursion(int max1, int max2) { Scanner in = new Scanner(System.in); int n = in.nextInt(); //   if (n > 0) { //   /   if (max1 < n) { recursion(n, max1); } //   /   else if (max2 < n) { recursion(max1, n); } //   /   else { recursion(max1, max2); } } else { System.out.println(max2); } } public static void main(String[] args) { recursion(0, 0); //    } }

P：最大値に等しい要素の数

自然数のシーケンス（行ごとに1つの数字）が与えられ、数字の0で終了します。このシーケンスの要素がその最大要素と等しい数を決定します。

このタスクではグローバル変数を使用できません。この関数は、データをパラメーターとして受け取るのではなく、キーボードから読み取ることでデータを受け取ります。 Pythonプログラムでは、関数は複数の数値のタプルの形式で結果を返しますが、関数はパラメーターをまったく受け取りません。 C ++プログラムでは、結果は変数に書き込まれ、参照によって関数に渡されます。関数は、値を返すために使用されるパラメーター以外のパラメーターを受け取りません。

シーケンスに少なくとも1つの数値（ゼロを除く）が含まれていることが保証されます。

解決策

 public class Solution { public static void recursion(int max, int count) { java.util.Scanner in = new java.util.Scanner(System.in); int n = in.nextInt(); //   if (n > 0) { //   /   if (n > max) { recursion(n, 1); } //   /   else if (n == max) { recursion(max, ++count); } //   /   else { recursion(max, count); } } else { System.out.println(count); } } public static void main(String[] args) { recursion(0, 0); //    } }

Q：ユニット数

一連の自然数（1行に1つの数字）が与えられ、2つの数字0が連続して終わる。このシーケンスで数値1が何回出現するかを決定します2つのゼロに続く数値は無視する必要があります。

このタスクでは、関数に渡されたグローバル変数とパラメーターを使用できません。この関数は、キーボードからデータを読み取ることでデータを受け取りますが、パラメーターとしては受け取りません。

解決策

 public class Solution { public static int recursion() { Scanner in = new Scanner(System.in); int n = in.nextInt(); //   if (n == 1) { int m = in.nextInt(); //   if (m == 1) { //   /   return recursion() + n + m; } else { int k = in.nextInt(); //   if (k == 1) { //   /   return recursion() + n + m + k; } else { return n + m + k; } } } else { int m = in.nextInt(); //   if (m == 1) { //   /   return recursion() + n + m; } else { return n + m; } } } public static void main(String[] args) { System.out.println(recursion()); //    } }

R：三角シーケンス

各自然数kが正確にk回発生する単調なシーケンスが与えられます：1、2、2、3、3、3、4、4、4、4、...

正の整数nを指定すると、このシーケンスの最初のnメンバーを出力します。 forループを1つだけ使用して取得してください。

解決策

 public class Solution { public static String recursion(int n) { int sum = 0; int j = 0; //   if (n == 1) { System.out.print("1"); } else { for (int i = 1; sum < n; i++) { sum += i; j = i; } //   /   System.out.print(recursion(--n) + " " + j); } return ""; } public static void main(String[] args) { recursion(5); //    } }

S：事前設定された桁数

自然数kとsが与えられます。桁の合計がdであるk桁の正の整数がいくつあるかを判別します。自然数を書くことは、数字0から始めることはできません。

このタスクでは、ループを使用して、特定の位置のすべての数字を反復処理できます。

解決策

 public class Solution { public static int recursion(int len, int sum, int k, int s) { //   if (len == k) { if (sum == s) { return 1; } else { return 0; } } int c = (len == 0 ? 1 : 0); int res = 0; //   /   for (int i = c; i < 10; i++) { res += recursion(len + 1, sum + i, k, s); } return res; } public static void main(String[] args) { System.out.println(recursion(0, 0, 3, 15)); //    } }

T：2つのゼロなし

番号aとbが与えられます。 2つのゼロが並んでいないaゼロとbユニットのシーケンスの数を決定します。

解決策

 public class Solution { public static int recursion(int a, int b) { //   if (a > b + 1) { return 0; } //   if (a == 0 || b == 0) { return 1; } //   /   return recursion(a, b - 1) + recursion(a - 1, b - 1); } public static void main(String[] args) { System.out.println(recursion(5, 8)); //    } }

U：番号Uターン

数値nが与えられ、その10進レコードにはゼロが含まれていません。同じ番号で書かれた番号を取得しますが、順序は逆です。

この問題を解決する場合、ループ、文字列、リスト、配列は使用できません。再帰と整数演算のみが許可されます。

関数はプログラムの結果である整数を返さなければなりません;一度に1桁の数字を出力することはできません。

Eivindからの更新

解決策

 public class Solution { public static int recursion(int n, int i) { return (n==0) ? i : recursion( n/10, i*10 + n%10 ); } public static void main(String[] args) { System.out.println(recursion(158, 0)); } }

以上です。問題を解決することで、私と同じくらいの喜びがもたらされることを願っています！

この記事は本質的に有益であり、主に再帰の経験があまりない人向けに設計されています。

そしてもちろん、私が書いた問題の解決策は、最も効果的で理解しにくいかもしれないことに注意してください。コメントでオプションを確認すると便利で興味深いでしょう。

また、フィードバックとコメントにも非常に満足しています。

ありがとうございます！

PS：最後に、再帰についてのジョークと再帰についてのジョーク

再帰。 面白いパズル

再帰の概要

タスク

再帰の問題を解決するには？

More articles:

再帰。面白いパズル