reglas - ¿Cómo puedo construir una función recursiva en python?

reglas de recursividad

Question

Esta pregunta ya tiene una respuesta aquí:

• Conceptos básicos de recursión en Python 3 respuestas

¿Cómo puedo construir una función recursiva en python?

Answer 1

Digamos que quieres construir: u (n + 1) = f (u (n)) con u (0) = u0

Una solución es definir una función recursiva simple:

u0 = ...

def f(x):
  ...

def u(n):
  if n==0: return u0
  return f(u(n-1))

Desafortunadamente, si desea calcular valores altos de u, se encontrará con un error de desbordamiento de la pila.

Otra solución es un bucle simple:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  return ux

Pero si quiere valores múltiples de u para diferentes valores de n, esto no es óptimo. Puede almacenar en caché todos los valores de una matriz, pero puede encontrarse con un error de falta de memoria. Es posible que desee utilizar generadores en su lugar:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  yield ux

for val in u(1000):
  print val

Hay muchas otras opciones, pero supongo que estas son las principales.

Answer 2

Ejemplo de función recursiva:

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

Ejecútelo con:

recursive("Hello world", 0)

Answer 3

La recursión en Python funciona igual que la recursión en otro idioma, con la construcción recursiva definida en términos de sí misma:

Por ejemplo, una clase recursiva podría ser un árbol binario (o cualquier árbol):

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'')

Como ya se mencionó, una estructura recursiva debe tener una condición de terminación. En esta clase, no es tan obvio porque solo recurre si se agregan nuevos elementos, y solo lo hace una sola vez extra.

También vale la pena señalar que, por defecto, Python tiene un límite para la profundidad de recursión disponible, para evitar absorber toda la memoria de la computadora. En mi computadora esto es 1000. No sé si esto cambia dependiendo del hardware, etc. Para ver el suyo:

import sys
sys.getrecursionlimit()

y para establecerlo:

import sys #(if you haven''t already)
sys.setrecursionlimit()

editar: No puedo garantizar que mi árbol binario sea el diseño más eficiente de la historia. Si alguien puede mejorarlo, me gustaría saber cómo

Answer 4

Me pregunto si querías decir "recursivo". Aquí hay un ejemplo simple de una función recursiva para calcular la función factorial :

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

Los dos elementos clave de un algoritmo recursivo son:

• La condición de terminación: n == 0
• El paso de reducción donde la función se llama a sí misma con un número más pequeño cada vez: factorial(n - 1)