Рекурсия.

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

В следующем примере переписывается функция bin() в рекурсивном варианте:

Def bin(n):

 """Цифры двоичного представления натурального числа """.

 if n == 0:

  return [].

 n, d = divmod(n, 2).

 return bin(n) + [d].

Print bin(69).

Здесь видно, что цикл while больше не используется, а вместо него появилось условие окончания рекурсии: условие, при выполнении которого функция не вызывает себя.

Конечно, в погоне за красивым рекурсивным решением не следует упускать из виду эффективность реализации. В частности, пример реализации функции для вычисления n–го числа Фибоначчи это демонстрирует:

Def Fib(n):

 if n < 2:

  return n.

 else:

  return Fib(n–1) + Fib(n–2).

В данном случае количество рекурсивных вызовов растет экспоненциально от числа n, что совсем не соответствует временной сложности решаемой задачи.

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

Предупреждение: При работе с рекурсивными функциями можно легко превысить глубину допустимой в Python рекурсии. Для настройки глубины рекурсии следует использовать функцию setrecursionlimit(N) из модуля sys, установив требуемое значение N.