Как построить рекурсивную функцию в python?

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

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

Двумя ключевыми элементами рекурсивного алгоритма являются:

• Условие завершения: n == 0.
• Шаг редукции, на котором функция каждый раз вызывает себя с меньшим числом: факториал(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()

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

Допустим, вы хотите построить: 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)