3 Рекурсия

                      Эпиграф:
                        void ShortStory()
                        {
                            cout<<"У попа была собака, он ее любил."<<endl;
                            cout<<"Она съела кусок мяса, он ее убил,"<<endl;
                            cout<<"В землю закопал и надпись написал:"<<endl;
                            ShortStory();
                        }

Функции в современных языках программирования могут вызывать другие функции. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n(n-1)!. Но как вычислить (n-1)! ? Если бы мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)(n-2)!. А как вычислить (n-2)! ? Если бы... В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на C++ или Питоне:

     // C++
     int factorial (int n)
     {
         if (n==0)
             return 1;
         else
             return n*factorial(n-1);
     }
     
     # Python
     def factorial (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. Оцените время работы этой функции в зависимости от n.
2. Напишите функцию возведения в степень, которая работала бы как для положительных, так и для отрицательных значений n: a^-n=1/aⁿ.
3. Напишите функцию быстрого возведения в степень, которая пользовалась бы следующими свойствами: aⁿ=(a^n/2)² при четном n, aⁿ=a*a^n-1 при нечетном n. Оцените время работы этой функции в зависимости от n.
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. Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: C_n^k=C_n-1^k-1+C_n-1^k. Вычислите значение C_n^k пользуясь этой формулой и учитывая, что C_n⁰=C_nⁿ=1.
6. Головоломка "Ханойские башни" состоит из трех колышков, пронумерованных числами 1, 2, 3. На колышек 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного колышка на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку с колышка 1 на колышек 2 за минимальное число перекладываний.

   Напишите программу, которая решает головоломку – для данного числа дисков n печатает последовательность перекладываний в формате "Диск 1 переложить с колышка 1 на колышек 2". Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

   

   Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков? Из трех дисков? Из четырех дисков? Напишите функцию move (n, x, y), которая печатает последовательность перемещаемых дисков для перекладывания пирамидки высоты n с колышка номер x на колышек номер y.