Recursive procedure c. Recursion. Training tasks
In order not to write one huge article, where there will be numerous examples of recursion in C++, I will write one more example of recursion here. By by and large Those who understand the basics and use of direct recursion in their functions can skip this material. Here is an example of using recursion, as in the article Functions in C++ for Beginners. Recursion
Problem 1 – Using recursion, display the factorial of a number from 1 to N
Writing code
=============================
STAGE No. 1 write an empty program
=============================
#include
#include
#include
int main()
{
system("cls");
getch();
return 0 ;
}
An empty program has been created, I think there is no need to comment
STAGE No. 2 we write we write the recursive function itself
=========================================
#include
#include
#include
//Our recursive function
int fact (int N )
{
//0! = 1, 1!=1, 2!=2, 3!=6... Because the first 2 numbers are ones and are not in strict sequence, we force this point in the code
if n<2
return 1
;
else return n * fact(n–1)
//here the function calls itself
}
int main()
{
system("cls");
cout<
getch();
return 0 ;
}
ddd
============
The main piece in a C++ recursion program
return n * fact(n–1)
Our function recalculates to obtain the previous value. The real value is the parameter passed to n from the point of the function call. The point of calling our function is to call it from the main block of the program. In our case, we call it from a function int main()
Why am I writing not the next one, but the previous one? When numbers are multiplied, then first 0 * 1 here is our current value 1, and zero is the previous calculation value. This is the whole essence of recursion, we calculate the present value using the previous one, while the previous value is obtained by the same calculation. The compiler itself calculates the previous value and stores this value in memory. All we need to do is give instructions.
. Thanks to this feature of compilers, a function encountering an instruction to call itself (in our case fact(n–1)
)does not overwrite the parameter passed to n to calculate the function. The parameter passed to n it remains in memory. In this case, another memory area is additionally defined in which our recursive function performs recursive calculations to obtain the previous result.
May the programmers forgive me for such a chewed-up judgment. This is approximately how beginners perceive recursion.
I hope this C++ blog for beginners was useful to someone and helped someone understand the basic concept of a recursive function in C++
Note. In this article, as in the previous one, I did the calculation not from 1 to N, but to the value entered inside the program. The point is that I didn’t want to write an extra line of code and assumed that the user was already well versed in entering data and displaying it on the screen.
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, etc. The easiest way to see recursion is to point the Web camera at the computer monitor screen, naturally, after turning it on. Thus, the camera will record the image of the computer screen and display it on this screen, it will be something like a closed loop. As a result, we will observe something similar to a tunnel.
In programming, recursion is closely related to functions; more precisely, it is thanks to functions in programming that there is such a thing as recursion or a 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). Typical recursive problems are: finding n!, Fibonacci numbers. We have already solved such problems, but using loops, that is, iteratively. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using a recursive function. The whole solution comes down to solving the main or, as it is also called, the base case. There is such a thing as a recursion step or a recursive call. In the case where a recursive function is called to solve a complex problem (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. Let's develop a program that declares a recursive function that calculates n!
"stdafx.h" #include
cout
// code Code::Blocks
// Dev-C++ code
using namespace std; unsigned long int factorial(unsigned long int); // prototype of a recursive function int i = 1; // initializing a global variable to count the number of recursive calls unsigned long int result; // global variable for storing the returned result of the recursive function int main(int argc, char* argv) ( int n; // local variable for passing the entered number from the keyboard cout IN The data type is declared unsigned long int , since the value of the factorial increases very quickly, for example, already 10! = 3,628,800. If the size of the data type is not enough, then the result will be a completely incorrect value. The code declares more operators than are needed to find n!. This is done so that, after running, the program will show what happens at each step of the recursive calls. Please note the highlighted lines of code, lines 23, 24, 28 is a recursive solution to n!. Lines 23, 24 are the basic solution of a recursive function, that is, as soon as the value in the variable f will be equal to 1 or 0 (since we know that 1! = 1 and 0! = 1), the recursive calls will stop, and the values will begin to be returned for each recursive call. When the value for the first recursive call returns, the program will return the value of the calculated factorial. IN line 28 the factorial() function calls itself, but its argument is one less. The argument is reduced each time to reach a particular solution. The result of the program (see Figure 1).
Enter n!: 5 Step 1 Result= 0 Step 2 Result= 0 Step 3 Result= 0 Step 4 Result= 0 5!=120
Figure 1 - Recursion in C++
Based on the result of the program, each step is clearly visible and the result at each step is zero, except for the last recursive call. It was necessary to calculate five factorials. The program made four recursive calls, and on the fifth call the base case was found. And once the program had a solution to the base case, it solved the previous steps and output the overall result. In Figure 1, only four steps are visible because in the fifth step a partial solution was found, which ultimately returned the final solution, i.e. 120. Figure 2 shows the recursive calculation scheme 5!. The diagram clearly shows that the first result is returned when a particular solution is reached, but not immediately, after each recursive call.
Figure 2 - Recursion in C++
So to find 5! need to know 4! and multiply it by 5; 4! = 4 * 3! and so on. According to the scheme shown in Figure 2, the calculation will be reduced to finding a special case, that is, 1!, after which values will be returned to each recursive call in turn. The last recursive call will return the value 5!.
Let's rework the program for finding the factorial so as to obtain a table of factorials. To do this, we will declare a for loop in which we will call the recursive function.
cout // code Code::Blocks // fibonacci.cpp: defines the entry point for the console application. #include cout // code Code::Blocks cout int help_rod; // block for determining the number of the auxiliary rod, analyzing the numbers of the initial and final rod if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3;tower(// launching a recursive function for solving the Towers of Hanoi problem number, // a variable storing the number of disks that need to be moved basic_rod, // a variable storing the number of the rod on which the disks will initially be located help_rod , // a variable storing the number of the rod, which is used as an auxiliary final_rod); // variable storing the number of the rod to which the disks need to be moved return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condition for ending recursive calls ( cout Figure 5 shows an example of the Tower of Hanoi recursive program. First, we entered the number of disks equal to three, then we entered the base rod (first), and designated the final rod (third). Automatically the second rod became auxiliary. The program produced a result that completely coincides with the animated solution to this problem. Enter of numbers of disks: 3 Enter the number of basic rod: 1 Enter the number of final rod: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3 Figure 5 - Recursion in C++ In programming, recursion is closely related to functions; more precisely, it is thanks to functions in programming that there is such a thing as recursion or a 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). A lot has been said about recursion. Here are some good resources: from the network Any algorithm implemented in recursive form can be rewritten in iterative form and vice versa. The question remains whether this is necessary and how effective it will be. To justify this, the following arguments can be given. To begin with, we can recall the definitions of recursion and iteration. Recursion is a way 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 program calls. After which we can conclude that they are mutually interchangeable, but not always with the same costs in terms of resources and speed. To justify this, we can give the following example: there is a function in which, in order to organize a certain algorithm, there is a loop that performs a sequence of actions depending on the current value of the counter (it may not depend on it). Since there is a cycle, it means that the body repeats a sequence of actions - iterations of the cycle. You can move operations into a separate subroutine and pass it the counter value, if any. Upon completion of the execution of the subroutine, we check the conditions for executing the loop, and if it is true, we proceed to a new call to the subroutine; if it is false, we complete the execution. Because We placed all the contents of the loop in a subroutine, which means that the condition for executing the loop is also placed in the subroutine, and it can be obtained through the return value of the function, parameters passed by reference or pointer to the subroutine, as well as global variables. Further, it is easy to show that a call to a given subroutine from a loop can be easily converted into a call or non-call (returning a value or simply completing work) of a subroutine from itself, guided by some conditions (those that were previously in the loop condition). Now, if you look at our abstract program, it roughly looks like passing values to a subroutine and using them, which the subroutine will change when it finishes, i.e. we replaced the iterative loop with a recursive call to a subroutine to solve a given algorithm. The task of bringing recursion to an iterative approach is symmetrical. To summarize, we can express the following thoughts: for each approach there is its own class of tasks, which is determined by the specific requirements for a specific task. You can find out more about this So the recursive function consists of Public class Solution ( public static int recursion(int n) ( // exit condition // Base case // when to stop repeating the recursion? if (n == 1) ( return 1; ) // Recursion step / recursive condition return recursion( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // call a recursive function ) ) Here the Basic condition is the condition when n=1. Since we know that 1!=1 and to calculate 1! we don't need anything. To calculate 2! we can use 1!, i.e. 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 factorial value of a number n, it is enough to multiply the factorial value of the previous number by n. Tags: Enter of numbers of disks: 3 Enter the number of basic rod: 1 Enter the number of final rod: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3 Figure 5 - Recursion in C++ In programming, recursion is closely related to functions; more precisely, it is thanks to functions in programming that there is such a thing as recursion or a 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). A lot has been said about recursion. Here are some good resources: from the network Any algorithm implemented in recursive form can be rewritten in iterative form and vice versa. The question remains whether this is necessary and how effective it will be. To justify this, the following arguments can be given. To begin with, we can recall the definitions of recursion and iteration. Recursion is a way 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 program calls. After which we can conclude that they are mutually interchangeable, but not always with the same costs in terms of resources and speed. To justify this, we can give the following example: there is a function in which, in order to organize a certain algorithm, there is a loop that performs a sequence of actions depending on the current value of the counter (it may not depend on it). Since there is a cycle, it means that the body repeats a sequence of actions - iterations of the cycle. You can move operations into a separate subroutine and pass it the counter value, if any. Upon completion of the execution of the subroutine, we check the conditions for executing the loop, and if it is true, we proceed to a new call to the subroutine; if it is false, we complete the execution. Because We placed all the contents of the loop in a subroutine, which means that the condition for executing the loop is also placed in the subroutine, and it can be obtained through the return value of the function, parameters passed by reference or pointer to the subroutine, as well as global variables. Further, it is easy to show that a call to a given subroutine from a loop can be easily converted into a call or non-call (returning a value or simply completing work) of a subroutine from itself, guided by some conditions (those that were previously in the loop condition). Now, if you look at our abstract program, it roughly looks like passing values to a subroutine and using them, which the subroutine will change when it finishes, i.e. we replaced the iterative loop with a recursive call to a subroutine to solve a given algorithm. The task of bringing recursion to an iterative approach is symmetrical. To summarize, we can express the following thoughts: for each approach there is its own class of tasks, which is determined by the specific requirements for a specific task. You can find out more about this So the recursive function consists of Public class Solution ( public static int recursion(int n) ( // exit condition // Base case // when to stop repeating the recursion? if (n == 1) ( return 1; ) // Recursion step / recursive condition return recursion( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // call a recursive function ) ) Here the Basic condition is the condition when n=1. Since we know that 1!=1 and to calculate 1! we don't need anything. To calculate 2! we can use 1!, i.e. 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 factorial value of a number n, it is enough to multiply the factorial value of the previous number by n. Tags: Add tagsBriefly 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, etc. One way to see recursion is to point the Web camera at the computer monitor screen, naturally, having first turned it on. Thus, the camera will record the image of the computer screen and display it on this screen, it will be something like a closed loop. As a result, we will observe something similar to a tunnel.
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 recursion problems. Tasks
When learning recursion, the most effective way to understand recursion is to solve problems. How to solve recursion problems?
First of all, you need to understand that recursion is a kind of overkill. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using a recursive function.
Just like an enumeration (cycle), recursion must have a stopping condition - Base case (otherwise, just like a cycle, recursion will work forever - infinite). This condition is the case to which the recursion goes (recursion step). At each step, a recursive function is called until the next call triggers the base 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 where a recursive function is called to solve a complex problem (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.
Let's look at this using the example of finding the factorial:
Add tags 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, etc. One way to see recursion is to point the Web camera at the computer monitor screen, naturally, having first turned it on. Thus, the camera will record the image of the computer screen and display it on this screen, it will be something like a closed loop. As a result, we will observe something similar to a tunnel.
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 recursion problems. Tasks
When learning recursion, the most effective way to understand recursion is to solve problems. How to solve recursion problems?
First of all, you need to understand that recursion is a kind of overkill. Generally speaking, everything that is solved iteratively can be solved recursively, that is, using a recursive function.
Just like an enumeration (cycle), recursion must have a stopping condition - Base case (otherwise, just like a cycle, recursion will work forever - infinite). This condition is the case to which the recursion goes (recursion step). At each step, a recursive function is called until the next call triggers the base 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 where a recursive function is called to solve a complex problem (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.
Let's look at this using the example of finding the factorial:
