Geekly Articles each Day

再垰。 面癜いパズル

こんにちは、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最埌に、 再垰 に぀いおのゞョヌクず再垰に぀いおのゞョヌク

Source: https://habr.com/ru/post/J275813/

More articles:


All Articles