Рекурсия
В С функции могут вызывать сами себя. Функция является рекурсивной, если оператор в теле функции вызывает функцию, содержащую данный оператор. Иногда называемая круговым определением, рекурсия является процессом определения чего-либо с использованием самой себя.
Простым примером является функция factr(), вычисляющая факториал целого числа. Факториал числа N является произведением чисел от 1 до N. Например, факториал 3 равен 1*2*3 или 6. Как factr(), так и его итеративный эквивалент показаны ниже:
/* Вычисление факториала числа */
int factr(int n) /* рекурсивно */
int answer;
if(n==1) return(1);
answer = factr(n-1)*n;
return(answer);
>
/* Вычисление факториала числа */
int fact (int n) /* нерекурсивно */
int t, answer;
answer == 1;
for(t=1; t answer=answer*(t);
return(answer);
>
Действие нерекурсивной версии fact() должно быть совершенно очевидно. Она использует цикл, начиная с 1 и заканчивая указанным числом, последовательно перемножая каждое число на ранее полученное произведение.
Действие рекурсивной функции factr() немного более сложно. Когда factr() вызывается с аргументом 1, функция возвращает 1. В противном случае она возвращает произведение factr(n- 1) * n. Для вычисления этого значения factr() вызывается с n-1. Это происходит, пока n не станет равно 1.
При вычислении факториала числа 2, первый вызов factr() приводит ко второму вызову с аргументом 1. Данный вызов возвращает 1, после чего результат умножается на 2 (исходное значение n). Ответ, таким образом, будет 2. Можно попробовать вставить printf() в factr() для демонстрации уровней и промежуточных ответов каждого вызова.
Когда функция вызывает сама себя, в стеке выделяется место для новых локальных переменных и параметров. Код функции работает с данными переменными. Рекурсивный вызов не создает новую копию функции. Новыми являются только аргументы. Поскольку каждая рекурсивно вызванная функция завершает работу, то старые локальные переменные и параметры удаляются из стека и выполнение продолжается с точки, в которой было обращение внутри этой же функции. Рекурсивные функции вкладываются одна в другую как элементы подзорной трубы.
Рекурсивные версии большинства подпрограмм могут выполняться немного медленнее, чем их итеративные эквиваленты, поскольку к необходимым действиям добавляются вызовы функций. Но в большинстве случаев это не имеет значения. Много рекурсивных вызовов в функции может привести к переполнению стека. Поскольку местом для хранения параметров и локальных переменных функции является стек и каждый новый вызов создает новую копию переменных, пространство стека может исчерпаться. Если это произойдет, то возникнет ошибка — переполнение стека.
Основным преимуществом применения рекурсивных функций является использование их для более простого создания версии некоторых алгоритмов по сравнению с итеративными эквивалентами. Например, сортирующий алгоритм Quicksort достаточно трудно реализовать итеративным способом. Некоторые проблемы, особенно связанные с искусственным интеллектом, также используют рекурсивные алгоритмы. Наконец, некоторым людям кажется, что думать рекурсивно гораздо легче, чем итеративно.
При написании рекурсивных функций следует иметь оператор if, чтобы заставить функцию вернуться без рекурсивного вызова. Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно. Это наиболее типичная ошибка, связанная с написанием рекурсивных функций. Надо использовать при разработке функции printf() и getchar(), чтобы можно было узнать, что происходит, и прекратить выполнение в случае обнаружения ошибки.
Что такое рекурсия в с
Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.
Рекурсивная функция факториала
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .
Определим метод для нахождения факториала:
int Factorial(int n)
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант , с которого начинается вычисление функции. В случае с факториалом это факториал числа 1, который равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта применяется оператор return :
if (n == 1) return 1;
То есть, если вводимое число равно 1, то возвращается 1
Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:
return n * Factorial(n - 1);
Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.
Используем эту функцию:
int Factorial(int n) < if (n == 1) return 1; return n * Factorial(n - 1); >int factorial4 = Factorial(4); // 24 int factorial5 = Factorial(5); // 120 int factorial6 = Factorial(6); // 720 Console.WriteLine($"Факториал числа 4 = "); Console.WriteLine($"Факториал числа 5 = "); Console.WriteLine($"Факториал числа 6 = ");
Рассмотрим поэтапно, что будет в случае вызова Factorial(4) .
-
Сначала идет проверка, равно ли число единице:
if (n == 1) return 1;
Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код
return n * Factorial(n - 1);
То есть фактически мы имеем:
return 4 * Factorial(3);
Factorial(3)
Опять же n не равно 1, поэтому выполняется код
return n * Factorial(n - 1);
То есть фактически:
return 3 * Factorial(2);
Factorial(2)
Опять же n не равно 1, поэтому выполняется код
return n * Factorial(n - 1);
То есть фактически:
return 2 * Factorial(1);
Factorial(1)
Теперь n равно 1, поэтому выполняется код
if (n == 1) return 1;
В итоге выражение
Factorial(4)
В реальности выливается в
4 * 3 * 2 * Factorial(1)
Рекурсивная функция Фибоначчи
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:
int Fibonachi(int n) < if (n == 0 || n == 1) return n; return Fibonachi(n - 1) + Fibonachi(n - 2); >int fib4 = Fibonachi(4); int fib5 = Fibonachi(5); int fib6 = Fibonachi(6); Console.WriteLine($"4 число Фибоначчи = "); Console.WriteLine($"5 число Фибоначчи = "); Console.WriteLine($"6 число Фибоначчи = ");
Здесь базовый вариант выглядит следующий образом:
if (n == 0 || n == 1) return n;
То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения Fibonachi(n — 1) + Fibonachi(n — 2);
Рекурсии и циклы
Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:
static int Fibonachi2(int n) < int result = 0; int b = 1; int tmp; for (int i = 0; i < n; i++) < tmp = result; result = b; b += tmp; >return result; >
В то же время в некоторых ситуациях рекурсия предоставляет элегантное решение, например, при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.
Рекурсия в С++
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи мы уже решали, но с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!
// factorial.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; cout unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout
// factorial.cpp: определяет точку входа для консольного приложения. #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; cout unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout
В строках 7, 9, 21 объявлен тип данных unsigned long int , так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение. В коде объявлено больше операторов, чем нужно, для нахождения n!. Это сделано для того, чтобы, отработав, программа показала, что происходит на каждом шаге рекурсивных вызовов. Обратите внимание на выделенные строки кода, строки 23, 24, 28 — это рекурсивное решение n!. Строки 23, 24 являются базовым решением рекурсивной функции, то есть, как только значение в переменной f будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 28 функция factorial() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения. Результат работы программы (см. Рисунок 1).
CppStudio.com
Enter n!: 5 Step 1 Result= 0 Step 2 Result= 0 Step 3 Result= 0 Step 4 Result= 0 5!=120
Рисунок 1 — Рекурсия в С++
По результату работы программы хорошо виден каждый шаг и результат на каждом шаге равен нулю, кроме последнего рекурсивного обращения. Необходимо было вычислить пять факториал. Программа сделала четыре рекурсивных обращения, на пятом обращении был найден базовый случай. И как только программа получила решение базового случая, она порешала предыдущие шаги и вывела общий результат. На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.
Рисунок 2 — Рекурсия в С++
Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.
Переделаем программу нахождения факториала так, чтобы получить таблицу факториалов. Для этого объявим цикл for , в котором будем вызывать рекурсивную функцию.
// factorial.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; for (int k = 1; k system("pause"); return 0; > unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout
// factorial.cpp: определяет точку входа для консольного приложения. #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv[]) < int n; // локальная переменная для передачи введенного числа с клавиатуры cout > n; for (int k = 1; k return 0; > unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! < if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout
В строках 16 — 19 объявлен цикл, в котором вызывается рекурсивная функция. Всё ненужное в программе закомментированно. Запустив программу, нужно ввести значение, до которого необходимо вычислить факториалы. Результат работы программы показан на рисунке 3.
CppStudio.com
Enter n!: 14 1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320 9!=362880 10!=3628800 11!=39916800 12!=479001600 13!=6227020800 14!=87178291200
Рисунок 3 — Рекурсия в С++
Теперь видно, насколько быстро возрастает факториал, кстати говоря, уже результат 14! не правильный, это и есть последствия нехватки размера типа данных. Правильное значение 14! = 87178291200.
Рассмотрим ещё одну типичную задачу — нахождение чисел Фибоначчи, используя рекурсию. Далее приведен код рекурсивного решения такой задачи. Вводим в ком строке порядковый номер числа из ряда Фибоначчи, и программа найдёт все числа из ряда Фибоначчи порядковые номера которых меньше либо равны введённого.
// fibonacci.cpp: определяет точку входа для консольного приложения. #include "stdafx.h" #include // библиотека для форматирования выводимой информации на экран #include using namespace std; unsigned long fibonacci(unsigned long);// прототип рекурсивной функции поиска чисел из ряда Фибоначчи int main(int argc, char* argv[]) < unsigned long entered_number; cout > entered_number; for (int counter = 1; counter unsigned long fibonacci(unsigned long entered_number) // функция принимает один аргумент < if ( entered_number == 1 || entered_number == 2) // частный случай return (entered_number -1); // ряд чисел Фибоначчи всегда начинается с 0, 1, . return fibonacci(entered_number-1) + fibonacci(entered_number-2); // формула поиска н-го числа, например найти восьмое по счёту число, и оно равно 7-е + 6-е >
// fibonacci.cpp: определяет точку входа для консольного приложения. #include // библиотека для форматирования выводимой информации на экран #include using namespace std; unsigned long fibonacci(unsigned long);// прототип рекурсивной функции поиска чисел из ряда Фибоначчи int main(int argc, char* argv[]) < unsigned long entered_number; cout > entered_number; for (int counter = 1; counter unsigned long fibonacci(unsigned long entered_number) // функция принимает один аргумент < if ( entered_number == 1 || entered_number == 2) // частный случай return (entered_number -1); // ряд чисел Фибоначчи всегда начинается с 0, 1, . return fibonacci(entered_number-1) + fibonacci(entered_number-2); // формула поиска н-го числа, например найти восьмое по счёту число, и оно равно 7-е + 6-е >
В строке 6 подключена библиотека для того, чтобы воспользоваться функцией setw() , которая в свою очередь выравнивает первый столбец чисел, то есть номера. Как мы можем заметить, сначала числа однозначные от 1 – 9, а потом идут двузначные. Если убрать данную функцию, то произойдет сдвиг влево чисел от 1 и до 9. Результат работы программы (см. Рисунок 4).
CppStudio.com
Enter number from the Fibonacci series: 30 1 = 0 2 = 1 3 = 1 4 = 2 5 = 3 6 = 5 7 = 8 8 = 13 9 = 21 10 = 34 11 = 55 12 = 89 13 = 144 14 = 233 15 = 377 16 = 610 17 = 987 18 = 1597 19 = 2584 20 = 4181 21 = 6765 22 = 10946 23 = 17711 24 = 28657 25 = 46368 26 = 75025 27 = 121393 28 = 196418 29 = 317811 30 = 514229
Рисунок 4 — Рекурсия в С++
Решение сводится к разбиению сложной задачи к двум более простым. Например, чтобы найти третье число из ряда Фибоначчи, необходимо сначала найти первое и второе, а потом сложить их. Первое число является частным случаем и равно 0 (нулю), второе число также является частным случаем и равно 1. Следовательно, третье число из ряда Фибоначчи равно сумме первого и второго = 1. Приблизительно так же рассуждала запрограммированная нами рекурсивная функция поиска чисел ряда Фибоначчи.
Разработаем ещё одну рекурсивную программу, решающую классическую задачу — «Ханойская башня». Даны три стержня, на одном из которых находится стопка n-го количества дисков, причём диски имеют не одинаковый размер (диски различного диаметра) и расположены таким образом, что по мере прохождения, сверху вниз по стержню диаметр дисков постепенно увеличивается. То есть диски меньшего размера должны лежать только на дисках большего размера. Необходимо переместить эту стопку дисков с начального стержня на любой другой из двух оставшихся (чаще всего это третий стержень). Один из стержней использовать как вспомогательный. Перемещать можно только по одному диску, при этом диск большего размера никогда не должен находиться над диском меньшего размера.
Допустим необходимо переместить три диска с первого стержня на третий, значит второй стержень вспомогательный. Визуальное решение данной задачи реализовано во Flash. Нажмите на кнопку start , чтобы запустить анимацию, кнопку stop , чтобы остановить.
Программу надо написать для n-го количества дисков. Так как мы решаем данную задачу рекурсивно, то для начала необходимо найти частные случаи решения. В данной задаче частный случай только один – это когда необходимо переместить всего один диск, и в этом случае даже вспомогательный стержень не нужен, но на это просто не обращаем внимания. Теперь необходимо организовать рекурсивное решение, в случае, если количество дисков больше одного. Введём некоторые обозначения, для того, чтоб не писать лишнего:
— стержень, на котором изначально находятся диски (базовый стержень);
— вспомогательный или промежуточный стержень;
— финальный стержень – стержень, на который необходимо переместить диски.
Далее, при описании алгоритма решения задачи будем использовать эти обозначения. Чтобы переместить три диска с на нам необходимо сначала переместить два диска с на а потом переместить третий диск(самый большой) на , так как свободен.
Для того, чтобы переместить n дисков с на нам необходимо сначала переместить n-1 дисков с на а потом переместить n-й диск(самый большой) на , так как свободен. После этого необходимо переместить n-1 дисков с на , при этом использовать стержень как вспомогательный. Эти три действия и есть весь рекурсивный алгоритм. Этот же алгоритм на псевдокоде:
n-1 переместить на
n переместить на
n-1 переместить с на , при этом использовать как вспомогательный
// hanoi_tower.cpp: определяет точку входа для консольного приложения. // Программа, рекурсивно решающая задачу "Ханойская башня" #include "stdafx.h" #include #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int _tmain(int argc, _TCHAR* argv[]) < cout > number; cout > basic_rod; cout > final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2 ) help_rod = 2; else if (basic_rod != 1 && final_rod != 1 ) help_rod = 1; else if (basic_rod != 3 && final_rod != 3 ) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски system("pause"); return 0; > void tower(int count_disk, int baza, int help_baza, int new_baza) < if ( count_disk == 1) // условие завершения рекурсивных вызовов < cout " else < tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный >>
// hanoi_tower.cpp: определяет точку входа для консольного приложения. // Программа, рекурсивно решающая задачу "Ханойская башня" #include #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int main() < cout > number; cout > basic_rod; cout > final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2 ) help_rod = 2; else if (basic_rod != 1 && final_rod != 1 ) help_rod = 1; else if (basic_rod != 3 && final_rod != 3 ) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски return 0; > void tower(int count_disk, int baza, int help_baza, int new_baza) < if ( count_disk == 1) // условие завершения рекурсивных вызовов < cout " else < tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный >>
На рисунке 5 показан пример работы рекурсивной программы Ханойская башня. Сначала мы ввели количество дисков равное трём, потом ввели базовый стержень (первый), и обозначили конечный стержень (третий). Автоматически второй стержень стал вспомогательным. Программа выдала такой результат, что он полностью совпадает с анимационным решением данной задачи.
CppStudio.com
Enter of numbers of disks: 3 Enter the number of basic rod: 1 Enter the number of final rod: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3
Рисунок 5 — Рекурсия в С++
Из рисунка видно, что сначала перемещается диск со стержня один на стержень три, потом со стержня один на стержень два, со стержня три на стержень два и т. д. То есть программа всего лишь выдает последовательность перемещений дисков и минимальное количество шагов, за которые будут перемещены все диски.
Все эти задачи можно было решить итеративно. Возникает вопрос: “Как лучше решать, итеративно или рекурсивно?”. Отвечаю: “Недостаток рекурсии в том, что она затрачивает значительно больше компьютерных ресурсов, нежели итерация. Это выражается в большой нагрузке, как на оперативную память, так и на процессор. Если очевидно решение той или иной задачи итеративным способом, то им и надо воспользоваться иначе, использовать рекурсию!” В зависимости от решаемой задачи сложность написания программ изменяется при использовании того или иного метода решения. Но чаще задача, решённая рекурсивным методом с точки зрения читабельности кода, куда понятнее и короче.
К сожалению, для данной темы пока нет подходящих задач. Если у вас есть таковые на примете, отправте их по адресу: admin@cppstudio.com. Мы их опубликуем!
Рекурсия
Рекурсия (recursion) — это поведение функции, при котором она вызывает сама себя. Такие функции называются рекурсивными. В отличие от цикла, они не просто повторяются несколько раз, а работают «внутри» друг друга.
Известная шутка гласит: «Чтобы понять рекурсию, надо понять рекурсию».
«IT-специалист с нуля» наш лучший курс для старта в IT
Рекурсия считается одним из основных понятий в информатике. Это метод решения задач, похожий на математическую индукцию: чтобы функция выполнилась, нужно сначала получить ее результат при вызове с другим значением.
Это работает так: функция A от единицы запускает функцию A от двойки, та — от тройки, и так далее, пока не будет высчитано нужное значение. Чтобы рекурсивный вызов закончился, нужно сразу прописать в функции A условие выхода из рекурсии: например, если получено какое-то значение, нужно не запускать функцию заново, а вернуть некоторый результат.
Если не прописать условие выхода, рекурсия будет бесконечной. А пока условие выхода не достигнуто, все вызванные экземпляры функции A будут работать одновременно — один вкладывает другой в себя.
Поддержка рекурсивного вызова есть практически во всех современных языках программирования.
Профессия / 8 месяцев
IT-специалист с нуля
Попробуйте 9 профессий за 2 месяца и выберите подходящую вам
Кто пользуется рекурсией и зачем она нужна
Рекурсия время от времени нужна программистам, чтобы решать различные задачи. Есть задания, которые проще и интуитивно понятнее решаются с ее помощью, а есть те, для которых есть более оптимальные алгоритмы.
Обычно рекурсию применяют при расчетах, которые подразумевают использование результата одного шага для подсчитывания другого. Например, расчет фрактала и его рисование. Зачастую подобные задачи можно решить и без рекурсии, но ее использование делает код проще, короче и быстрее, чем альтернативные варианты. Правда, рекурсия может слишком нагружать компьютер, поэтому такие решения применяют не всегда.
Рекурсию можно встретить и в других отраслях: физике, биологии, лингвистике и даже архитектуре. Например, фрактальные формы вроде листа папоротника или снежинки — рекурсивные. Вложенные предложения — тоже. А самый наглядный вид рекурсии — два поставленных друг напротив друга зеркала.
Программисты пользуются рекурсией и ради забавы. Например, известная аббревиатура GNU расшифровывается как GNU is Not Unix – первая буква скрывает под собой ту же аббревиатуру. Это тоже рекурсия.
Отличия рекурсии от цикла
На интуитивном уровне рекурсивный вызов легко перепутать с циклом. И то, и другое понятие подразумевает, что функция выполняется несколько раз. Но есть принципиальное различие:
- в цикле новые функции не вызываются внутри вызванных ранее;
- рекурсия же — это функция, вызывающая сама себя с другими аргументами.
Простыми словами: инструкция с пунктом «Вернись к пункту 1» — это цикл, инструкция с пунктом «Прочитай инструкцию заново» — рекурсия.
Но тем не менее циклами часто заменяют рекурсию, например в ситуациях, где рекурсивные алгоритмы оказываются слишком ресурсоемкими. Правда, для использования циклов в качестве замены рекурсии понадобятся дополнительные ухищрения.
Прерывание рекурсии
Если рекурсивной функции не задать условия для выхода, она будет работать бесконечно, пока огромное количество ее экземпляров не «съест» всю оперативную память устройства и не переполнит стек вызовов. Поэтому разработчик должен предусмотреть пути выхода из рекурсивного процесса.
Обычно путь выхода — это какое-то условие, которое проверяется в самом начале выполнения функции. Если оно выполняется, функция вызовет себя снова, если нет — выдаст какое-то значение, отдаст его предыдущему «соседу» и закроется.
Например, если n > 1, то вызвать A(n-1). Иначе вернуть 1. Получается, что когда n станет меньше или равен единице, то A не запустится заново — очередной экземпляр просто вернет единицу. Остальные экземпляры получат нужный себе результат и тоже закроются по каскаду. Этот процесс называется обратным ходом рекурсии. А то, что было до него, — прямым ходом.
Количество открытых в итоге функций называется глубиной рекурсии.
Пример рекурсии: расчет чисел Фибоначчи
Известный пример рекурсивных расчетов — числа Фибоначчи. Каждое следующее число в ряду — сумма двух предыдущих, начиная с 1.
Получается так: 1, 1, 2, 3, 5, 8, 13, 21 и так далее. Использование рекурсии здесь — напрашивающийся и интуитивно понятный способ расчета:
- допустим, функция называется fibonacci(n) и рассчитывает n-е по счету число Фибоначчи;
- на первом шаге функция вызывает fibonacci(n-1) и fibonacci(n-2), то есть себя, но с другими аргументами, и складывает получившиеся результаты;
- новые вызовы будут делать то же самое, пока n не дойдет до единицы или нуля — это первое число Фибоначчи, и в таком случае функция вернет 1;
- предыдущий экземпляр функции получит два результата 1 — от единицы и нуля, сложит их и отправит «назад» к более ранним соседям;
- в итоге все вызванные функции получат от своих «потомков» ответ, сложат полученные значения и вернут их самой первой функции fibonacci(n);
- та сложит финальные значения, вернет результат и закроется.
Это только один простой пример; рекурсивных алгоритмов намного больше. Еще один известный — расчет факториала числа.
Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить
Другие примеры рекурсивных расчетов
- Вычисление факториала числа — последовательных умножений на предыдущее число. Например, 3! (факториал от трех) — это 1 * 2 * 3.
- Расчет и изображение фракталов — конструкций, где более мелкие элементы повторяют более крупные. Яркие примеры фракталов — снежинка и лист папоротника.
- Обход ветвящихся структур данных, например графов и деревьев.
- Компьютерный анализ естественного языка, фраз и предложений.
- Поиск пути в лабиринте и построение маршрутов — к примеру, алгоритмы DFS и BFS.
- Вычисления с числовыми рядами, например те же числа Фибоначчи или поиск простых чисел.
- Математические операции, требующие повторяющихся действий с разными значениями, к примеру возведение в степень больше 2, поиск максимума или минимума.
- Операции с системами счисления, к примеру перевод чисел из одной в другую.
За пределами математики и информатики можно вспомнить много других примеров рекурсии: от самовозбуждения электронных схем до сказок «Тысячи и одной ночи».
Прямая и косвенная рекурсия
Рекурсию можно условно разделить на прямую и косвенную.
- Прямая вызывает сама себя напрямую. То есть функция A вызывает функцию A с другими аргументами.
- Косвенная действует через «третью» функцию. Функция A вызывает функцию B, а та в свою очередь снова вызывает функцию A. Это тоже рекурсия, просто менее очевидная.
Еще бывают линейная и каскадная рекурсии. В линейной экземпляр функции вызывает сам себя только один раз, в каскадной — несколько. Например, расчет чисел Фибоначчи — каскадная рекурсия, потому что функция вызывает себя дважды: для n-1 и n-2.
Рекурсивный и итеративный процессы
Одну и ту же рекурсию можно использовать по-разному. Например, есть понятия рекурсивного и итеративного процесса. И там, и там применяется рекурсия, но различается подход к ней.
В рекурсивном процессе все расчеты откладываются «на потом», как в примере с числами Фибоначчи. Конечный расчет делает тот экземпляр функции, который вызвали в последнюю очередь, а потом результаты по каскаду передаются предыдущим.
В итеративном процессе все наоборот. Функция считает всё, что может посчитать, и только потом вызывает свой новый экземпляр и передает наработки ему.
Частный случай рекурсии — хвостовая: в ней вызов самой себя — последнее, что делает функция, перед тем как завершиться.
Преимущества рекурсии
Рекурсивный подход многим нравится, потому что он изящный и емкий, а описать такой алгоритм часто быстрее, чем аналоги. Вот основные преимущества создания рекуррентных решений.
Ясность. Прочитать рекурсивный код обычно проще, чем программу, полную ухищрений для решения той же задачи без рекурсии. Это важный плюс, если речь идет о коммерческом программировании, где код часто смотрят другие люди.
Наглядность. Некоторые задачи, вроде тех же чисел Фибоначчи или факториалов, — рекурсивные по самому своему определению. То же самое касается задач на ряды, фракталы и так далее. Решить такую задачу через рекурсию — один из наиболее наглядных и интуитивно понятных способов. Более того: люди пользуются рекурсией все время, даже просто когда разговаривают, и это лишний раз работает на интуитивное ее понимание.
Краткость. Рекурсивная функция обычно короче, чем реализация без рекурсии. Разработчику проще и удобнее написать несколько строк кода, чем создавать огромную программу, тратить время и силы и путаться в написанном.
Красота. Наконец, сам концепт многие считают красивым и изящным. Это и правда так — посмотрите на фракталы и снежинки: в них есть определенная красота. Рекурсию используют даже в искусстве: от матрешек до сложных узоров, украшающих готические соборы.
Недостатки рекурсии
Недостатков у рекурсивного подхода два, но они критичные и серьезно ограничивают применение этой концепции даже там, где она напрашивается.
Риск переполнения. При всем перечисленном программисты пользуются рекурсией довольно осторожно. Она устроена так, что, пока не выполнится последний вызов функции, все предыдущие не завершатся — ведь они как бы «вкладывают» в себя последующие. Поэтому такие программы отнимают много ресурсов компьютера. Так что разработчики смотрят и на параметр производительности и решают, что выгоднее в конкретном случае — использовать рекурсию или нет.
Риск бесконечности. Если что-то пошло не так и программист случайно получил бесконечную рекурсию, единственный выход — принудительно закрыть программу. А потом переписать ее, чтобы ошибка не повторялась при следующем запуске.
Чем пользоваться: рекурсией или циклом
Недостатки выше — не повод отказываться от рекурсивных решений совсем. Просто в каждом случае, где можно применить рекурсию, разработчик должен спрашивать себя, оптимально это или нет.
- Если программе важна высокая скорость работы и низкая нагрузка или существует риск переполнения памяти — лучше выбрать вариант без рекурсии.
- Если скорость не так важна, а реализация без рекурсии отнимет много времени и строк кода — лучше воспользоваться рекурсивным подходом.
Понимание, что лучше использовать в конкретном случае, приходит с опытом. Начинающим разработчикам в любом случае стоит освоить рекурсию: это важная часть программирования и информатики вообще.
Как начать работать с рекурсией
Концепт и примеры рекурсивных функций можно найти в любом учебнике по программированию. Обычно начинающим предлагают потренироваться на простых «классических» задачах вроде чисел Фибоначчи или расчета факториала. Затем можно переходить к более сложным заданиям: обход графа, анализ текста или что-либо еще. А какой язык выбрать — зависит от ваших предпочтений и пожеланий к отрасли.
Если вы хотите познакомиться с большим количеством концептов из информатики — записывайтесь на курсы! Вы узнаете, как работают разные процессы, и сделаете первые шаги к новой востребованной профессии.
IT-специалист с нуля
Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.