Функции и процедуры. Рекурсия

Формулировка задачи очень проста: требуется возвести число a в степень n. Проще всего, конечно, умножить число a на себя нужное число раз. Этот алгоритм потребует n-1 умножений. Можно ли существенно ускорить, этот алгоритм? Оказывается, да. Заметим, что если мы хотим вычислить, например, a¹⁰, то, вычислив на некотором шаге a⁵, можно умножить его на себя и, тем самым, сэкономить несколько умножений. Такой трюк можно использовать для любой четной степени, что позволяет написать формулы, аналогичные формуле из предыдущей задачи:

 

Эта формула позволяет написать рекурсивную функцию вычисления степени (не забывая о терминальном условии n=1).

 

 

 

 

Итак, подведём некоторые итоги.

·         Рекурсия – это прием программирования, при котором функция (процедура) вызывает сама себя.

·         Для того, чтобы этот процесс вызовов не зацикливался, в функции обязательно должно быть терминальное условие – при выполнении такого условия процесс рекурсивных вызовов прерывается.

·         Любой рекурсивный алгоритм можно реализовать и не прибегая к рекурсии, но рекурсия позволяет записывать многие алгоритмы в более простой форме. При этом рекурсивные алгоритмы обычно более требовательны к ресурсам (памяти), чем нерекурсивные.