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

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

Me pregunto si te referías a “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 menor cada vez: factorial(n - 1)

La recursión en Python funciona igual que la recursión en otro idioma, con el constructo recursivo definido en términos de sí mismo:

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 se repite si se agregan nuevos elementos, y solo lo hace una vez extra.

También vale la pena mencionar que, de forma predeterminada, Python tiene un límite a 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 tuyo:

 import sys sys.getrecursionlimit() 

y para configurarlo:

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

edición: no puedo garantizar que mi árbol binario sea el diseño más eficiente de todos. Si alguien puede mejorarlo, me encantaría saber cómo

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 stack.

Otra solución es un simple bucle:

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

Pero si desea múltiples valores de u para diferentes valores de n, esto es subóptimo. Podría almacenar en caché todos los valores en 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.

Ejemplo de función recursiva:

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

Ejecutarlo con:

 recursive("Hello world", 0)