5.7 Рекурсивные функции

Как было отмечено выше, функция может в свою очередь обращаться к другой функции. Но функция также может вызывать и саму себя ! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что по определению 0!=1, 1!=1. А как вычислить величину n! для большого значения числа n ?

Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=(n-1)!∙n. Но как вычислить (n-1)! ? Если бы мы вычислили (n-2)!, то мы смогли бы вычислить и (n-1)!=(n-1)∙(n-2)! А как вычислить (n-2)! и т.д. ? В конце рассуждений мы дойдем до величины 0!, которая равна 1.

Таким образом, для вычисления факториала числа n мы можем использовать значение факториала числа (n-1). Это оказывается возможным реализовать и в программе на C++:

int factorial (int n)

{

if (n==0)

return 1;

else

return (n*factorial(n-1));

}

Подобный прием - вызов функцией самой себя - называется рекурсией, а сама функция называется рекурсивной.

Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны. Также часто использование рекурсии приводит к ошибкам, наиболее распространенная из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не закончится свободная память в компьютере.

Две наиболее распространенные причины для бесконечной рекурсии:

1. неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if (n==0), то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т.д. до бесконечности;

2. рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получится бесконечная цепочка вызовов.

Поэтому при разработке рекурсивной функции необходимо прежде всего правильно оформить условия завершения рекурсии и определиться с ответом на вопрос, почему рекурсия когда-либо все же завершит работу.

Упражнения

1. Напишите рекурсивную функцию возведения в степень, пользующуюся следующим свойством: aⁿ=a∙a^n-1.

2. Напишите функцию возведения в степень, которая работала бы для отрицательных значений n: a^-n=1/aⁿ.

3. Напишите функцию быстрого возведения в степень, которая пользовалась бы следующими свойствами: aⁿ=(a^n/2)² при четном n, aⁿ=a∙a^n-1 при нечетном n. Подумайте, сколько умножений выполнит эта функция для вычисления aⁿ ?

4. Последовательность Фибоначчи определена следующим образом: φ₀=1, φ₁=1, φ_n=φ_n-1+φ_n-2 при n>1. Начало ряда Фибоначчи выглядит следующим образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Напишите функцию int Phi(int n), которая по данному натуральному n возвращает φ_n.

5.8 Рекурсивные функции. Задача о Ханойской башне (факультативно)

Рассмотрим известную задачу о Ханойских Башнях. Для решения этой задачи можно воспользоваться рекурсивными функциями.

Итак, сначала все же про башни, а про программирование позже. По официальной версии, Ханойские Башни — это головоломка, которую в 1883 г. придумал французский математик Эдуард Люка. Для тех, кто не знает, суть головоломки заключается в следующем: есть три стержня и восемь дисков разных диаметров, вначале все диски собраны на одном стержне так, что меньшие диски лежат на больших. Люка предлагал переложить все диски с первого стержня на третий, используя при этом второй.

При этом следует соблюдать следующее правило: диски можно перекладывать с одного стержня на другой, при этом нельзя класть диск поверх диска меньшего радиуса. По той же официальной версии, ради повышения интереса к своей головоломке Люка придумал легенду, повествующую про башню Брамы, увеличенную копию Ханойской. Эта башня состояла из 64 золотых дисков, а стержни были вырезаны из алмаза. Так вот, башни Брамы были созданы не иначе, как при Сотворении мира, и с того времени жрецы в храме трудятся, перекладывая диски по описанной выше методике. По легенде, как только они закончат процесс перекладывания, наступит конец света, и потому жрецы очень стараются …

Для решения этой задачи можно предложить следующий алгоритм. Для того, чтобы перенести самый большой диск, нужно сначала перенести все диски, кроме последнего, на второй стержень, потом перенести самый большой - на третий диск, после чего останется перенести все остальные диски со второго на третий. Задачу о переносе N-1 дисков решим аналогично, только поменяем стержни местами (при первом переносе конечным стержнем будем считать второй, а не третий, при втором переносе начальным вместо первого будет второй).

Таким образом, задача разрешима. Действительно, задачу о переносе N-1 дисков сведем к задаче о переносе N-2 дисков, ту в свою очередь - к задаче о N-3 дисков, и так вплоть до последнего – 1-ого диска. Также ясно, что это единственно правильный подход, который легко реализовать, используя рекурсию.

Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура Ch_B(n,i,j,w), печатающая перемещения дисков, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i,j,w} = {1,3,2}.

// задача о ханойских башнях как пример использования рекурсивной функции

#include <iostream>

using namespace std;

void Ch_B(int, int, int, int); // объявление рекурсивной функции

int main()

{

int n;

cin>>n; // считываем количество дисков

Ch_B(n,1,2,3);

return 0;

}

void Ch_B(int n, int i, int j, int w) // описание рекурсивной функции

{

if (n>1)

{

Ch_B(n-1,i,w,j);

Ch_B(1,i,j,w);

Ch_B(n-1,w,j,i);

}

else cout<<”i=”<<i<<” ==> ”<<”j=”<<j<<endl; // печать текущего перемещения

// диска

return;

}

Последовательность вызовов процедуры Ch_B при m=3 иллюстрируется древовидной структурой на приведенном ниже рисунке. Каждый раз при вызове процедуры Ch_B под параметры n, i, j, w выделяется память и запоминается место возврата.

При возврате из процедуры Ch_B память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рис. Последовательность вызовов процедуры Ch_B