Как я могу построить рекурсивную функцию в python?
Как я могу построить рекурсивную функцию в python?
Ответ 1
Мне интересно, означает ли вы "рекурсивный". Вот простой пример рекурсивной функции для вычисления факториальной функции :
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Два ключевых элемента рекурсивного алгоритма:
- Условие завершения:
n == 0
- Шаг восстановления, когда функция вызывает себя с меньшим числом каждый раз:
factorial(n - 1)
Ответ 2
Рекурсия в Python работает так же, как рекурсия на другом языке, с рекурсивной конструкцией, определенной в терминах самого себя:
Например, рекурсивный класс может быть двоичным деревом (или любым деревом):
class tree():
def __init__(self):
'''Initialise the tree'''
self.Data = None
self.Count = 0
self.LeftSubtree = None
self.RightSubtree = None
def Insert(self, data):
'''Add an item of data to the tree'''
if self.Data == None:
self.Data = data
self.Count += 1
elif data < self.Data:
if self.LeftSubtree == None:
# tree is a recurive class definition
self.LeftSubtree = tree()
# Insert is a recursive function
self.LeftSubtree.Insert(data)
elif data == self.Data:
self.Count += 1
elif data > self.Data:
if self.RightSubtree == None:
self.RightSubtree = tree()
self.RightSubtree.Insert(data)
if __name__ == '__main__':
T = tree()
# The root node
T.Insert('b')
# Will be put into the left subtree
T.Insert('a')
# Will be put into the right subtree
T.Insert('c')
Как уже упоминалось, рекурсивная структура должна иметь условие завершения. В этом классе это не так очевидно, потому что оно повторяется только при добавлении новых элементов и делает это только один раз.
Также стоит отметить, что python по умолчанию имеет ограничение на доступность глубины рекурсии, чтобы не поглощать всю память компьютера. На моем компьютере это 1000. Я не знаю, меняется ли это в зависимости от аппаратного обеспечения и т.д. Чтобы увидеть ваше:
import sys
sys.getrecursionlimit()
и установить его:
import sys #(if you haven't already)
sys.setrecursionlimit()
edit: Я не могу гарантировать, что мое двоичное дерево является наиболее эффективным дизайном. Если кто-нибудь сможет его улучшить, я буду рад услышать, как
Ответ 3
Предположим, вы хотите построить: u (n + 1) = f (u (n)) с u (0) = u0
Одним из решений является определение простой рекурсивной функции:
u0 = ...
def f(x):
...
def u(n):
if n==0: return u0
return f(u(n-1))
К сожалению, если вы хотите вычислить большие значения u, вы столкнетесь с ошибкой.
Другим решением является простой цикл:
def u(n):
ux = u0
for i in xrange(n):
ux=f(ux)
return ux
Но если вы хотите несколько значений u для разных значений n, это неоптимально. Вы можете кэшировать все значения в массиве, но вы можете столкнуться с ошибкой вне памяти. Вместо этого вы можете использовать генераторы:
def u(n):
ux = u0
for i in xrange(n):
ux=f(ux)
yield ux
for val in u(1000):
print val
Есть много других опций, но я думаю, что это основные из них.
Ответ 4
Пример рекурсивной функции:
def recursive(string, num):
print "#%s - %s" % (string, num)
recursive(string, num+1)
Запустите его с помощью
recursive("Hello world", 0)