Как я могу создать рекурсивную функцию в Python? [дубликат]

Я задаюсь вопросом, имели ли Вы в виду "рекурсивный". Вот простой пример рекурсивной функции для вычислений функция факториала :

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

два основных элемента рекурсивного алгоритма:

• условие завершения: n == 0
• шаг сокращения, где вызовы функции сам с меньшим числом каждый раз: factorial(n - 1)

Рекурсия в 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()

редактирование: Я не могу гарантировать, что мое двоичное дерево является самым эффективным дизайном когда-либо. Если бы кто-либо может улучшить его, я был бы рад услышать как

Скажем, Вы хотите создать: 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

существует много других опций, но я предполагаю, что это основные.

Пример рекурсивной функции:

def recursive(string, num):
    print "#%s - %s" % (string, num)
    recursive(string, num+1)

Выполнение это с:

recursive("Hello world", 0)