Как пользоваться рекурсией?
Не могу понять рекурсию. Как написать терминальное выражение, как может функция вызвать саму себя? Нужно написать программу на С++ с помощью рекурсии.
Источник: Stack Overflow на русском
Ответы
как может функция вызвать саму себя?
В ее теле должен быть вызов самой себя. Естественно, этот вызов должен осуществляться по условию, иначе программа уйдет в нечто, похожее на бесконечный цикл, только хуже, чем бесконечный цикл.
Мне очень нравится пример из SICP, который позволяет найти квадратный корень методом Ньютона.
Представим, что некоторая функция Х принимает на вход число, от которого нужно найти квадратный корень, и число, которое мы предполагаем близким к этому корню, а в ответ функция возвращает число, которое гарантированно находится ближе к квадратному корню, нежели наше предположение. В таком случае мы будем вызывать эту функцию следующим образом:
найти_квадратный_корень(число, предположение, погрешность)
{
предположение = Х(число, предположение)
если модуль(число - (предположение в квадрате)) меньше погрешности
вернуть предположение
иначе
вернуть найти_квадратный_корень(число, предположение, погрешность)
}
таким образом функция вызывает сама себя, пока предположение не удовлетворит заданной погрешности.
Отлично написано:
Несколько просветляющих примеров рекурсии.
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);
}