Recursion Training tasks
Hello Habrahabr!
This article will focus on tasks for recursion and how to solve them.
Recursion is a fairly common phenomenon that occurs not only in the fields of science, but also in everyday life. For example, the Droste effect, the Sierpinski triangle, and so on. One of the options to see the recursion is to point the webcam at the computer monitor screen, of course, by turning it on beforehand. Thus, the camera will record the image of the computer screen, and display it on this screen, you get something like a closed loop. As a result, we will see something like a tunnel.
')
In programming, recursion is closely related to functions; more precisely, it is precisely due to functions in programming that there is such a thing as recursion or recursive function. In simple words, recursion is the definition of a part of a function (method) through itself, that is, it is a function that calls itself, directly (in its body) or indirectly (through another function).
Much has been said about recursion. Here are some good resources:
It is assumed that the reader is theoretically familiar with recursion and knows what it is. In this article we will pay more attention to the tasks on recursion.
When studying recursion, the most effective way to understand recursion is to solve problems.
First of all, you need to understand that recursion is a kind of bust. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using the recursive function.
Just like brute-force (cycle), recursion must have a stopping condition - Basic case (otherwise, like a cycle, a recursion will work forever - infinite). This condition is the case to which the recursion is going (recursion step). At each step, the recursive function is called until the next condition triggers the basic condition and the recursion stops (or rather, returns to the last function call). The whole solution comes down to solving the base case. In the case when the recursive function is called to solve a complex task (not the base case), a number of recursive calls or steps are performed, in order to reduce the problem to a simpler one. And so on until we get a basic solution.
So the recursive function consists of
Consider this on the example of finding factorial :
Here the basic condition is the condition when n = 1. Since we know that 1! = 1 and to calculate 1! we do not need anything. To calculate 2! we can use 1! 2! = 1! * 2. To calculate 3! we need 2! * 3 ... To calculate n! we need (n-1)! * n. This is the recursion step. In other words, to get the value of the factorial from the number n, it is enough to multiply by n the value of the factorial from the previous number.
The network in explaining recursion also gives the problem of finding the Fibonacci numbers and the Tower of Hanoi
Let us now consider tasks with different levels of complexity.
Try to solve them yourself using the method described above. When deciding, try thinking recursively. What is the base case in the problem? Which recursion step or recursive condition?
Go! Problem solutions are provided in Java.
A: From 1 to n
Given a positive integer n. Print all numbers from 1 to n.
B: A to B
Given two integers A and B (each on a separate line). Output all numbers from A to B inclusive, in ascending order, if A <B, or in descending order otherwise.
C: Ackermann function
In computability theory, the Ackermann function A (m, n) plays an important role, defined as follows:
Two non-negative integers m and n are given, each on a separate line. Output A (m, n).
D: Exact degree of two
Given a natural number N. Output the word YES if the number N is an exact power of two, or the word NO otherwise.
The operation of exponentiation can not be used!
E: Sum of digits
Given a natural number N. Calculate the sum of its numbers.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course).
F: Numbers from right to left
Given a natural number N. Print all its digits one by one, in reverse order, separated by spaces or new lines.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course). Only recursion and integer arithmetic is allowed.
G: Numbers from left to right
Given a natural number N. Print all its digits one by one, in the usual order, separated by spaces or new lines.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course). Only recursion and integer arithmetic is allowed.
H: Checking the number for simplicity
Given a positive integer n> 1. Check whether it is simple. The program should output the word YES if the number is prime and NO, if the number is composite. The algorithm must have complexity O (logn).
Note. It is clear that the task itself is non-recursive, since checking the number n for simplicity does not boil down to checking the simplicity of smaller numbers. Therefore, we need to make another recursion parameter: a divisor of the number, and it is for this parameter that recursion is to be done.
I: Factorization
Given a positive integer n> 1. Print all prime factors of this number in non-decreasing order, taking into account the multiplicity. The algorithm must have complexity O (logn).
J: Palindrome
Given a word consisting of only lowercase Latin letters. Check if the word is palindrome. Output YES or NO.
When solving this problem, it is impossible to use cycles, in solutions on python it is impossible to use slices with a step other than 1.
K: Print odd numbers of a sequence
Given a sequence of natural numbers (one number per line), ending with a number 0. Output all odd numbers from this sequence, keeping their order.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function does not return a value, but immediately displays the result on the screen. The main program should consist only of a call to this function.
L: Print odd-numbered sequence members.
Given a sequence of natural numbers (one number per line), ending with the number 0. Output the first, third, fifth, etc. from the entered numbers. The final zero should not be displayed.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function does not return a value, but immediately displays the result on the screen. The main program should consist only of a call to this function.
M: Maximum sequence
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the highest value of the number in this sequence.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function returns a single value: the maximum of the read sequence. It is guaranteed that the sequence contains at least one number (except zero).
N: Mean Sequence
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the average value of the elements of this sequence (excluding the last zero).
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns a tuple of a pair of numbers: the number of elements in the sequence and their sum. In a C ++ program, the result is recorded in two variables, which are passed to the function by reference.
It is guaranteed that the sequence contains at least one number (except zero).
O: The second maximum
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the value of the second largest element in this sequence, that is, the element that will be greatest if you delete the largest element from the sequence.
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns the result as a tuple of several numbers, and the function does not receive any parameters at all. In a C ++ program, the result is written to variables, which are passed to the function by reference. Other parameters, except as used to return the value, the function does not receive.
It is guaranteed that the sequence contains at least two numbers (except zero).
P: The number of elements equal to the maximum
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine how many elements of this sequence are equal to its largest element.
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns the result as a tuple of several numbers, and the function does not receive any parameters at all. In a C ++ program, the result is written to variables, which are passed to the function by reference. Other parameters, except as used to return the value, the function does not receive.
It is guaranteed that the sequence contains at least one number (except zero).
Q: Number of units
Given a sequence of natural numbers (one number per line), ending with two numbers 0 in a row. Determine how many times the number 1 appears in this sequence. The numbers following two zeros must be ignored.
In this task, you cannot use global variables and parameters passed to the function. The function receives data by reading it from the keyboard, rather than receiving it as parameters.
R: Triangle sequence
Given a monotone sequence in which every positive integer k occurs exactly k times: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...
Given this natural n, print the first n members of this sequence. Try to do with just one for loop.
S: Specified amount of numbers
Given the natural numbers k and s. Determine how many k-valued positive integers exist whose sum of digits is d. Writing a natural number can not begin with the number 0.
In this task, you can use a loop to iterate through all the numbers in a position.
T: No two zeros
Given the numbers a and b. Determine how many sequences there are of a zeros and b ones in which no two zeros stand side by side.
U: Number reversal
Given the number n, the decimal notation does not contain zeros. Get the number written in the same numbers, but in the opposite order.
When solving this problem, it is impossible to use cycles, strings, lists, arrays, only recursion and integer arithmetic are allowed.
The function must return an integer that is the result of the program, it is impossible to display a number by one digit.
Update from Eivind
That's all. I hope the solution of problems brought you as much pleasure as I did!
The article is informative and mainly intended for people who do not have much experience with recursion.
And of course, I note that the solutions to the problems written by me may not be the most effective and easy to understand. It would be useful and interesting to see your options in the comments.
I would also be very happy for your feedback and comments.
Thank!
PS: And lastly jokes about recursion and jokes about recursion
This article will focus on tasks for recursion and how to solve them.
Briefly about recursion
Recursion is a fairly common phenomenon that occurs not only in the fields of science, but also in everyday life. For example, the Droste effect, the Sierpinski triangle, and so on. One of the options to see the recursion is to point the webcam at the computer monitor screen, of course, by turning it on beforehand. Thus, the camera will record the image of the computer screen, and display it on this screen, you get something like a closed loop. As a result, we will see something like a tunnel.
')
In programming, recursion is closely related to functions; more precisely, it is precisely due to functions in programming that there is such a thing as recursion or recursive function. In simple words, recursion is the definition of a part of a function (method) through itself, that is, it is a function that calls itself, directly (in its body) or indirectly (through another function).
Much has been said about recursion. Here are some good resources:
- from habr
- wikipedia
- wikibooks
- Recursion and recursive tasks. Recursion areas
- Recursive algorithms. Recursion areas
- The benefits of recursion
- Recursion Notes
- Notes on recursion - 2. A look at the recursion from the inside
It is assumed that the reader is theoretically familiar with recursion and knows what it is. In this article we will pay more attention to the tasks on recursion.
Tasks
When studying recursion, the most effective way to understand recursion is to solve problems.
How to solve the problem of recursion?
First of all, you need to understand that recursion is a kind of bust. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using the recursive function.
from the network
Any algorithm implemented in a recursive form can be rewritten in an iterative form and vice versa. The question remains whether this is necessary and how effective it will be.
To substantiate you can make such arguments.
To begin with, we can recall the definition of recursion and iteration. Recursion is a method of organizing data processing in which a program calls itself directly, or with the help of other programs. Iteration is a way of organizing data processing, in which certain actions are repeated many times without leading to recursive calls of programs.
Then we can conclude that they are mutually interchangeable, but not always with the same cost of resources and speed. For justification, you can give an example: there is a function in which there is a cycle for organizing a certain algorithm that performs a sequence of actions depending on the current value of the counter (it may not depend on it). Once there is a cycle, it means that the sequence of actions is repeated in the body - a loop iteration. You can make the operation in a separate subroutine and pass it the value of the counter, if any. Upon completion of the execution of the subroutine, we check the conditions for the execution of the cycle, and if it is correct, go to a new subroutine call, if false, terminate the execution. Since we have placed the entire contents of the cycle in the subroutine, which means that the condition for the execution of the cycle is also placed in the subroutine, and it can be obtained through returning the value of the function, the parameters passed by reference or pointer to the subroutine, and global variables. Further, it is easy to show that a call from this cycle can easily be converted from a cycle to a call, or not a call (return value or just completion of work) from the subprogram itself, guided by some conditions (those that were previously in the cycle condition). Now, if we look at our abstract program, it approximately looks like the transfer of values to a subroutine and their use, which the subroutine will change upon completion, i.e. we replaced the iterative loop with a recursive subroutine call to solve this algorithm.
The task of bringing recursion to an iterative approach is symmetrical.
Summing up, we can express such thoughts: for each approach there is a class of tasks, which is determined by the specific requirements for a specific task.
More details on this can be found here.
To substantiate you can make such arguments.
To begin with, we can recall the definition of recursion and iteration. Recursion is a method of organizing data processing in which a program calls itself directly, or with the help of other programs. Iteration is a way of organizing data processing, in which certain actions are repeated many times without leading to recursive calls of programs.
Then we can conclude that they are mutually interchangeable, but not always with the same cost of resources and speed. For justification, you can give an example: there is a function in which there is a cycle for organizing a certain algorithm that performs a sequence of actions depending on the current value of the counter (it may not depend on it). Once there is a cycle, it means that the sequence of actions is repeated in the body - a loop iteration. You can make the operation in a separate subroutine and pass it the value of the counter, if any. Upon completion of the execution of the subroutine, we check the conditions for the execution of the cycle, and if it is correct, go to a new subroutine call, if false, terminate the execution. Since we have placed the entire contents of the cycle in the subroutine, which means that the condition for the execution of the cycle is also placed in the subroutine, and it can be obtained through returning the value of the function, the parameters passed by reference or pointer to the subroutine, and global variables. Further, it is easy to show that a call from this cycle can easily be converted from a cycle to a call, or not a call (return value or just completion of work) from the subprogram itself, guided by some conditions (those that were previously in the cycle condition). Now, if we look at our abstract program, it approximately looks like the transfer of values to a subroutine and their use, which the subroutine will change upon completion, i.e. we replaced the iterative loop with a recursive subroutine call to solve this algorithm.
The task of bringing recursion to an iterative approach is symmetrical.
Summing up, we can express such thoughts: for each approach there is a class of tasks, which is determined by the specific requirements for a specific task.
More details on this can be found here.
Just like brute-force (cycle), recursion must have a stopping condition - Basic case (otherwise, like a cycle, a recursion will work forever - infinite). This condition is the case to which the recursion is going (recursion step). At each step, the recursive function is called until the next condition triggers the basic condition and the recursion stops (or rather, returns to the last function call). The whole solution comes down to solving the base case. In the case when the recursive function is called to solve a complex task (not the base case), a number of recursive calls or steps are performed, in order to reduce the problem to a simpler one. And so on until we get a basic solution.
So the recursive function consists of
- Stop condition or Basic case
- The continuation condition or recursion step is a way to make the task more simple.
Consider this on the example of finding factorial :
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)); // } } Here the basic condition is the condition when n = 1. Since we know that 1! = 1 and to calculate 1! we do not need anything. To calculate 2! we can use 1! 2! = 1! * 2. To calculate 3! we need 2! * 3 ... To calculate n! we need (n-1)! * n. This is the recursion step. In other words, to get the value of the factorial from the number n, it is enough to multiply by n the value of the factorial from the previous number.
The network in explaining recursion also gives the problem of finding the Fibonacci numbers and the Tower of Hanoi
Let us now consider tasks with different levels of complexity.
Try to solve them yourself using the method described above. When deciding, try thinking recursively. What is the base case in the problem? Which recursion step or recursive condition?
Go! Problem solutions are provided in Java.
A: From 1 to n
Given a positive integer n. Print all numbers from 1 to n.
Decision
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 to B
Given two integers A and B (each on a separate line). Output all numbers from A to B inclusive, in ascending order, if A <B, or in descending order otherwise.
Decision
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: Ackermann function
In computability theory, the Ackermann function A (m, n) plays an important role, defined as follows:
Two non-negative integers m and n are given, each on a separate line. Output A (m, n).
Decision
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: Exact degree of two
Given a natural number N. Output the word YES if the number N is an exact power of two, or the word NO otherwise.
The operation of exponentiation can not be used!
Decision
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: Sum of digits
Given a natural number N. Calculate the sum of its numbers.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course).
Decision
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: Numbers from right to left
Given a natural number N. Print all its digits one by one, in reverse order, separated by spaces or new lines.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course). Only recursion and integer arithmetic is allowed.
Decision
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: Numbers from left to right
Given a natural number N. Print all its digits one by one, in the usual order, separated by spaces or new lines.
When solving this problem, it is impossible to use strings, lists, arrays (well, and cycles, of course). Only recursion and integer arithmetic is allowed.
Decision
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: Checking the number for simplicity
Given a positive integer n> 1. Check whether it is simple. The program should output the word YES if the number is prime and NO, if the number is composite. The algorithm must have complexity O (logn).
Note. It is clear that the task itself is non-recursive, since checking the number n for simplicity does not boil down to checking the simplicity of smaller numbers. Therefore, we need to make another recursion parameter: a divisor of the number, and it is for this parameter that recursion is to be done.
Decision
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: Factorization
Given a positive integer n> 1. Print all prime factors of this number in non-decreasing order, taking into account the multiplicity. The algorithm must have complexity O (logn).
Decision
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: Palindrome
Given a word consisting of only lowercase Latin letters. Check if the word is palindrome. Output YES or NO.
When solving this problem, it is impossible to use cycles, in solutions on python it is impossible to use slices with a step other than 1.
Decision
Another solution
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")); // } } Another solution
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: Print odd numbers of a sequence
Given a sequence of natural numbers (one number per line), ending with a number 0. Output all odd numbers from this sequence, keeping their order.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function does not return a value, but immediately displays the result on the screen. The main program should consist only of a call to this function.
Decision
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: Print odd-numbered sequence members.
Given a sequence of natural numbers (one number per line), ending with the number 0. Output the first, third, fifth, etc. from the entered numbers. The final zero should not be displayed.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function does not return a value, but immediately displays the result on the screen. The main program should consist only of a call to this function.
Decision
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: Maximum sequence
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the highest value of the number in this sequence.
In this task, you cannot use global variables and pass any parameters to the recursive function. The function receives data by reading it from the keyboard. The function returns a single value: the maximum of the read sequence. It is guaranteed that the sequence contains at least one number (except zero).
Decision
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: Mean Sequence
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the average value of the elements of this sequence (excluding the last zero).
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns a tuple of a pair of numbers: the number of elements in the sequence and their sum. In a C ++ program, the result is recorded in two variables, which are passed to the function by reference.
It is guaranteed that the sequence contains at least one number (except zero).
Decision
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: The second maximum
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine the value of the second largest element in this sequence, that is, the element that will be greatest if you delete the largest element from the sequence.
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns the result as a tuple of several numbers, and the function does not receive any parameters at all. In a C ++ program, the result is written to variables, which are passed to the function by reference. Other parameters, except as used to return the value, the function does not receive.
It is guaranteed that the sequence contains at least two numbers (except zero).
Decision
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: The number of elements equal to the maximum
Given a sequence of natural numbers (one number per line), ending with the number 0. Determine how many elements of this sequence are equal to its largest element.
You cannot use global variables in this task. The function receives data by reading it from the keyboard, rather than receiving it as a parameter. In the Python program, the function returns the result as a tuple of several numbers, and the function does not receive any parameters at all. In a C ++ program, the result is written to variables, which are passed to the function by reference. Other parameters, except as used to return the value, the function does not receive.
It is guaranteed that the sequence contains at least one number (except zero).
Decision
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: Number of units
Given a sequence of natural numbers (one number per line), ending with two numbers 0 in a row. Determine how many times the number 1 appears in this sequence. The numbers following two zeros must be ignored.
In this task, you cannot use global variables and parameters passed to the function. The function receives data by reading it from the keyboard, rather than receiving it as parameters.
Decision
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: Triangle sequence
Given a monotone sequence in which every positive integer k occurs exactly k times: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...
Given this natural n, print the first n members of this sequence. Try to do with just one for loop.
Decision
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: Specified amount of numbers
Given the natural numbers k and s. Determine how many k-valued positive integers exist whose sum of digits is d. Writing a natural number can not begin with the number 0.
In this task, you can use a loop to iterate through all the numbers in a position.
Decision
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: No two zeros
Given the numbers a and b. Determine how many sequences there are of a zeros and b ones in which no two zeros stand side by side.
Decision
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: Number reversal
Given the number n, the decimal notation does not contain zeros. Get the number written in the same numbers, but in the opposite order.
When solving this problem, it is impossible to use cycles, strings, lists, arrays, only recursion and integer arithmetic are allowed.
The function must return an integer that is the result of the program, it is impossible to display a number by one digit.
Update from Eivind
Decision
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)); } } That's all. I hope the solution of problems brought you as much pleasure as I did!
The article is informative and mainly intended for people who do not have much experience with recursion.
And of course, I note that the solutions to the problems written by me may not be the most effective and easy to understand. It would be useful and interesting to see your options in the comments.
I would also be very happy for your feedback and comments.
Thank!
PS: And lastly jokes about recursion and jokes about recursion
Source: https://habr.com/ru/post/275813/
All Articles