I can not understand recursion. How to write a terminal expression, how can a function call itself? You need to write a C ++ program using recursion, but I don’t understand a damn thing.

  • one
    To understand recursion, you need to understand recursion. It's obvious how much, it's obvious. Just writing a program using recursion will not work (although you may even think), maybe you just need to write a program with recursion? - KoVadim
  • There are many examples of using recursion. The most common of these is factorial calculation, where each step of the execution of the same function depends on the result of the previous one. - Ni55aN
  • To begin with, accept the rule that all the data that the recursive function operates on (except for those needed only for intermediate calculations in one of its calls) are passed in the function arguments. Do not use any external (extern / static, class data if the function is a class method) with respect to it when developing an algorithm. Then, when you get comfortable, you yourself will understand how and when in a recursive function you can operate with non-local variables. - avp
  • Yes, a program with recursion, replacing multiplication with addition of ones, that is, you need to add one as many times as you need to answer. Suppose 2 * 3 means 1 + 1 + 1 + 1 + 1 + 1 = 6 only recursively, without a while or for loop. - Sergos

3 answers 3

How can a function call itself?

In her body should be a challenge to herself. Naturally, this call should be carried out by condition, otherwise the program will go into something that looks like an infinite loop, only worse than an infinite loop.

I really like the example from SICP, which allows you to find the square root by the Newton method.
Imagine that some function X takes as input a number from which to find the square root and a number that we assume is close to this root, and in response, the function returns a number that is guaranteed to be closer to the square root than our assumption. In this case, we will call this function as follows:

найти_квадратный_корень(число, предположение, погрешность) { предположение = Х(число, предположение) если модуль(число - (предположение в квадрате)) меньше погрешности вернуть предположение иначе вернуть найти_квадратный_корень(число, предположение, погрешность) }

thus, the function calls itself until the assumption satisfies the given error.

  • I will write a program to replace the multiplication with addition of units, that is, you need to add a unit as many times as necessary to answer. Suppose 2 * 3 means 1 + 1 + 1 + 1 + 1 + 1 = 6 only recursively, without a while or for loop. That is, I understand that my case should call the function i ++ (adding one as needed for the correct answer). - Sergos
  • @Sergos, no, no plus one exists at all in multiplication. Multiplication a * b can be considered as the sum of b terms, each of which is a: a * b = E (i = 1; i = b) {a} = a [1] + a [2] + a [3] + a [4] + ... + a [b] In this case, the recursive function will have two arguments: a multiplied number and a multiplier. If the multiplier is 1, then the function returns the number itself; if the multiplier is greater than one, the function returns the result of calling itself for the multiplier by one less: - etki
  • function multiply (a, b) {if (b == 1) {return a; } return a + multiply (a, b - 1); } (the full version will be a bit longer, of course, plus the overflow will now be remembered): function multiply (a, b) {if (b == 0) {return 0; } if (b == 1) {return a; } if (b <0) {return -multiply (a, -b); } return a + multiply (a, b - 1); } - etki

Excellent written:

http://cppstudio.com/post/418/

    Some enlightening examples of recursion.

     int sum_digits(const int n) { return n < 10 ? n : n % 10 + sum_digits(n / 10); } void rev(void) { int c = getchar(); if (c != EOF) { rev(); putchar(c); } } int gcd(const int a, const int b) { return a == 0 ? b : gcd(b, a % b); } int max3(const int a, const int b, const int c) { if (a > b) { return max3(b, a, c); } if (b > c) { return max3(a, c, b); } return c; } int power(const int x, const int n) { return n == 0 ? 1 : x * power(x, n - 1); }