Лекции Булатицкий Дмитрий Иванович (во многом по материалам Прасолова А. Н.)
 Скачать 319.62 Kb.
|
Вычисление факториалаХорошей иллюстрацией механизма рекурсии является функция для вычисления факториала натурального числа. long RecFact(int n) { if(n<=1) return 1; // граничное условие return n* RecFact(n-1); } Данная функция использует рекурсивные обращения, что делает ее компактной, и основаной на очевидном соотношении: N! = (N-1)!*N Иными словами, чтобы получить значение факториала от числа N, достаточно умножить на N значение факториала от предыдущего числа: Числа ФибоначчиЧислами Фибоначчи называют элементы последовательности, в которой первые два числа равны: 0, 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи). Иногда число 0 не рассматривается как член последовательности. Иногда числа Фибоначчи рассматривают и для отрицательных значений n, как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе. Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования». На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что: изначально есть новорожденная пара кроликов (самец и самка), со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов, кролики никогда не умирают. Сколько пар кроликов будет через год? • В начале первого месяца есть только одна новорожденная пара (1). • В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1) • В конце второго месяца первая пара рождает новую пару и опять спаривается (2) • В конце третьего месяца первая пара рождает еще одну новую пару и спаривается, вторая пара только спаривается (3) • В конце четвертого месяца первая пара рождает еще одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5) В конце n-го месяца количество пар кроликов будет равно количеству пар в предыдущем месяце плюс количество новорожденных пар, которых будет столько же, сколько пар было два месяца назад. Таким образом: Fn = Fn-2 + Fn-1. Число Фибоначчи может быть вычислено с помощью рекурсивной функции: unsigned long Fib(unsigned n) { if(n==0) return 0; // граничное условие if(n==1) return 1; // граничное условие return Fib(n-2)+Fib(n-1); } Рекурсия и итерацияРекурсия достаточно широко применяется в программировании, что основано на рекурсивной природе многих математических алгоритмов. А также Вы должны знать, что любой рекурсивный алгоритм можно преобразовать в эквивалентный итеративный (то есть использующий циклические конструкции). В больших и сложных программах иногда приходится заменять рекурсию на итерацию. Дело в том, что рекурсия связана с многократными вызовами процедур, а это несколько менее эффективно при выполнении по сравнению с использованием циклов. Однако рекурсивные версии программ, как правило, гораздо короче и нагляднее. Так вместо приведённого выше рекурсивного вычисления факториала можно организовать итерационное. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно: N! = 1*2*3* . . . *(N-2)*(N-1)*N 1! = 1 0! = 1 long NonRecFact(int n) { int i; long res; //результат res= 1; for(i=1; i<=n; i++) { res*= i; } return res; } Выигрыш от перехода к нерекурсивному (итерационному) решению для задачи вычисления чисел Фибоначчи ещё значительнее. |