// Done by TheTutor -- 8/26/01
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
/* Итак, что же такое рекурсия? Это понятие не из языка C/C++. Рекурсию можно реализовать
на любом языке - рекурсия это больше логический процесс, который, когда используется
правильно, может облегчить выполнение задачи.
Рекурсия определяется всего лишь как вызов функцией самой себя внутри ее тела.
Вы запутались? Хорошо, очень быстрый пример рекурсии (который будет длится вечно и
приведет к зависанию компьютера).
void badRecursion()
{
printf("This will eventually crash\n");
badRecursion();
}
А теперь хороший пример рекурсии. Мы реализуем функцию факториал.
Проделаем простой математический пример.
Прежде всего, символ ! в математике означает "факториал". 3! читается как "три факториал".
Когда берется факториал числа, нужно взять все предыдущие числа начиная с единицы и перемножить.
Вот так:
3! = 1 * 2 * 3 = 6
Напишем функцию факториал с помощью рекурсии.
*/
#include <stdio.h>
typedef unsigned int uint; // Лень писать unsigned int, поэтому определим тип uint
uint factorial(uint num); // Наша функция факториал.
// Наша функция main довольно слабовата - она просто напечатает число 6 и программа завершится.
int main()
{
printf("%d\n",factorial(3));
return 0;
}
/* А теперь подумаем об определении факториала.
3! = 1 * 2 * 3 что эквивалентно 3 * (2!)
Мы знаем, что 1! = 1
Используя эти простые факты, напишем нашу функцию */
uint factorial(uint num)
{
// Факториал одного равен одному - таким образом возвращаем один
if(num == 1)
return 1;
else
return num * factorial(num - 1); // В другом случае возвращаем num * факториал (num - 1)
}
/* Итак, посмотрим шаг за шагом, что произойдет при вызове factorial(3):
factorial(3)
"num" не равен 1, поэтому возвращаем num * factorial(2) но перед
возвратом из функции, должен быть возврат из factorial(2)
factorial(2)
"num" не равен 1, поэтому возвращаем num * factorial(1) но перед
возвратом из функции, должен быть возврат из factorial(1)
factorial(1)
Здесь num равен 1, поэтому возвращаем 1
А теперь мы снова в "factorial(2)" на строчке "return num * factorial(1)"
Вспомните, что в factorial(2) "num" равен 2. И тогда у нас получается, что
num равен 2 и factorial(1) возвращает 1, то есть вызов factorial(2)
возвращает 2 (результат 2 * 1)
Теперь мы вновь в "factorial(3)" на строке "return num * factorial(2)".
В factorial(3) "num" равен 3, и то, что у нас есть это num равный 3 и factorial(2)
возвращает 2, и таким образом функция возвращает 6 (результат 3 * 2)
Не забывайте, каждый раз когда мы вызываем функцию, мы получаем ЛОКАЛЬНЫЕ копии
переменных, передаваемых в функции. Это значит, эти локальные копии известны только
конкретным вызовам функции.
*/
/*
| TheTutor
| thetutor@gametutorials.com
| © 2001 GameTutorials
*/
// Перевод © 2004 Евгений Казеко
// www.gamecoder.kazeko.com
// evgeniy@kazeko.com
|
