Рекурсия
Процедура или функция может содержать внутри себя вызов другой процедуры. В том числе, подпрограмма может вызывать саму себя. В этом случае компьютеру все равно. Он также как и всегда последовательно сверху вниз выполняет те команды, которые ему встретились.
Если вспомнить математику, то там можно встретить
принцип математической индукции. Он заключается в следующем:
некоторое утверждение справедливо для всякого натурального
n, если
1. оно справедливо для
n = 1 и
2. из справедливости утверждения для какого-либо произвольного натурального
n = k следует его справедливость для
n = k + 1.
В программировании этот прием называют
рекурсией.
Рекурсия - это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
Рекурсивной же будет называться процедура (функция), которая вызывает саму себя напрямую или через другие процедуры и функции.
Пример
def Rec(a):
if (a>0): Rec(a-1)
print(a)
Схематично работу рекурсии можно изобразить блок-схемой
Процедура Rec() выполняется с параметром 3. Затем внутри процедуры с параметром 3 вызывается процедура с параметром 2 и т.д., пока не произойдет вызов процедуры с параметром 0. При вызове процедуры с параметром 0 рекурсивного вызова уже не произойдет и процедуры с параметром 0 напечатает число 0 и закончит работу. Затем управление передается обратно в процедуру с параметром 1, она также заканчивает свою работу печатает число 1 и т.д. до процедуры с параметром 3.
Все вызвавшиеся процедуры хранятся в памяти, до тех пор пока не закончат свою работу. Количество одновременно работающих процедур называется
глубиной рекурсии.