ООП в Python - Рекурсия

Рекурсия - важное понятие, как функционального, так и объектно-ориентированного программирования. При рекурсии происходит самореференция функции, т.е. функция вызывает саму себя. Поставите друг напротив друга два зеркала: в них образуются два бесконечных "коридора" с повторяющимися отражениями. Это и есть рекурсия. Лучшим определением рекурсии будет являться такое изображение:

Классическим примером функции, реализуемой рекурсивно, является функция вычисления факториала, которая находит результат умножения всех натуральных чисел ниже заданного числа. Например, 5! (или факториал числа 5) означает:

5! = 5 * 4 * 3 * 2 * 1

или

5! = 5 * 4! 

4! = 4 * 3! 

3! = 3 * 2!

2! = 2 * 1!

1! = 1 - это базовый случай и не требует вычисления других фактоиалов.

Формула решения факториала:

n! = n*(n-1)!

Рассмотрим рекурсивную функцию решения факториала:

def factorial(x):
 if x == 1:
   return 1;
 else:
   return x * factorial(x - 1)
print(factorial(5))

Результат 120.

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

>>>
 RuntimeError: maximim recursion depth exceeded
>>>

Рекурсия может быть также непрямой. Первая функция вызывает вторую. Вторая вызывает первую, которая вызвает вторую и так далее. Можно задействовать больше функций.

def is_even(x):
 if x == 0:
   return True
 else:
   return is_odd(x-1)

def is_odd(x):
 return not is_even(x);

print(is_odd(17));
print(is_even(23));
>>>
 True
 False
>>>

not - это логический оператор, который возвращает логическое значение, обратное значению. return возвращает результат этого оператора. Другими словами, выражение следует читать как return (not self.myReturnCode). Оператор not дает True, если его аргумент ложный, False в противном случае.