Fundamentos de la recursión en Python

“Escriba una función recursiva,” listSum “que tome una lista de enteros y devuelva la sum de todos los enteros en la lista”.

Ejemplo:

>>>> listSum([1,3,4,5,6]) 19 

Sé cómo hacerlo de otra manera, pero no de forma recursiva.

 def listSum(ls): i = 0 s = 0 while i < len(ls): s = s + ls[i] i = i + 1 print s 

Necesito la forma básica de hacer esto, ya que no se permiten funciones especiales incorporadas.

Cuando enfrente un problema como este, intente express el resultado de la función con la misma función.

En su caso, puede obtener el resultado agregando el primer número con el resultado de llamar a la misma función con el rest de los elementos de la lista.

Por ejemplo,

 listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6]) = 1 + (3 + listSum([4, 5, 6])) = 1 + (3 + (4 + listSum([5, 6]))) = 1 + (3 + (4 + (5 + listSum([6])))) = 1 + (3 + (4 + (5 + (6 + listSum([]))))) 

Ahora, ¿cuál debería ser el resultado de listSum([]) ? Debería ser 0. Eso se llama condición base de su recursión. Cuando se cumple la condición base, la recursión llegará a su fin. Ahora, tratemos de implementarlo.

Lo principal aquí es, dividir la lista. Puedes usar rebanar para hacer eso.

Versión simple

 >>> def listSum(ls): ... # Base condition ... if not ls: ... return 0 ... ... # First element + result of calling `listsum` with rest of the elements ... return ls[0] + listSum(ls[1:]) >>> >>> listSum([1, 3, 4, 5, 6]) 19 

Recursión de la llamada de cola

Una vez que entienda cómo funciona la recursión anterior, puede intentar mejorarla un poco. Ahora, para encontrar el resultado real, también dependemos del valor de la función anterior. La statement de return no puede devolver inmediatamente el valor hasta que la llamada recursiva devuelva un resultado. Podemos evitar esto pasando la stream al parámetro de función, como esto

 >>> def listSum(ls, result): ... if not ls: ... return result ... return listSum(ls[1:], result + ls[0]) ... >>> listSum([1, 3, 4, 5, 6], 0) 19 

Aquí, pasamos cuál es el valor inicial de la sum para estar en los parámetros, que es cero en listSum([1, 3, 4, 5, 6], 0) . Luego, cuando se cumple la condición base, en realidad estamos acumulando la sum en el parámetro de result , por lo que la devolvemos. Ahora, la última statement de return tiene listSum(ls[1:], result + ls[0]) , donde agregamos el primer elemento al result actual y lo pasamos de nuevo a la llamada recursiva.

Este podría ser un buen momento para entender Tail Call . No sería relevante para Python, ya que no hace la optimización de llamadas Tail.


Pasando alrededor de la versión de índice

Ahora, podrías pensar que estamos creando tantas listas intermedias. ¿Puedo evitar eso?

Por supuesto que puede. Solo necesitas el índice del artículo para ser procesado a continuación. Pero ahora, la condición de base será diferente. Dado que vamos a pasar el índice, ¿cómo determinaremos cómo se ha procesado la lista completa? Bueno, si el índice es igual a la longitud de la lista, entonces hemos procesado todos los elementos en ella.

 >>> def listSum(ls, index, result): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6], 0, 0) 19 

Versión de función interna

Si observa la definición de la función ahora, le está pasando tres parámetros. Digamos que va a liberar esta función como una API. ¿Será conveniente para los usuarios pasar tres valores, cuando en realidad encuentren la sum de una lista?

No ¿Qué podemos hacer al respecto? Podemos crear otra función, que es local a la función listSum real y podemos pasarle todos los parámetros relacionados con la implementación, de esta manera

 >>> def listSum(ls): ... ... def recursion(index, result): ... if index == len(ls): ... return result ... return recursion(index + 1, result + ls[index]) ... ... return recursion(0, 0) ... >>> listSum([1, 3, 4, 5, 6]) 19 

Ahora, cuando se llama a listSum , simplemente devuelve el valor de retorno de recursion función interna de recursion , que acepta el index y los parámetros de result . Ahora solo estamos pasando esos valores, no los usuarios de listSum . Solo tienen que pasar la lista para ser procesados.

En este caso, si observa los parámetros, no estamos pasando ls a recursion sino que lo estamos utilizando en su interior. ls es accesible dentro de la recursion debido a la propiedad de cierre.


Versión de parámetros por defecto

Ahora, si desea que sea sencillo, sin crear una función interna, puede hacer uso de los parámetros predeterminados, como este

 >>> def listSum(ls, index=0, result=0): ... # Base condition ... if index == len(ls): ... return result ... ... # Call with next index and add the current element to result ... return listSum(ls, index + 1, result + ls[index]) ... >>> listSum([1, 3, 4, 5, 6]) 19 

Ahora, si la persona que llama no pasa ningún valor explícitamente, entonces 0 se asignará tanto al index como al result .


Problema de poder recursivo

Ahora, apliquemos las ideas a un problema diferente. Por ejemplo, intentemos implementar la función de power(base, exponent) . Devolvería el valor de base elevado al exponent potencia.

 power(2, 5) = 32 power(5, 2) = 25 power(3, 4) = 81 

Ahora, ¿cómo podemos hacer esto recursivamente? Tratemos de entender cómo se logran esos resultados.

 power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32 power(5, 2) = 5 * 5 = 25 power(3, 4) = 3 * 3 * 3 * 3 = 81 

Hmmm, así que tenemos la idea. La base multiplicada a sí misma, los tiempos de exponent dan el resultado. De acuerdo, ¿cómo lo abordamos? Intentemos definir la solución con la misma función.

 power(2, 5) = 2 * power(2, 4) = 2 * (2 * power(2, 3)) = 2 * (2 * (2 * power(2, 2))) = 2 * (2 * (2 * (2 * power(2, 1)))) 

¿Cuál debería ser el resultado si algo se eleva al poder 1? El resultado será el mismo número, ¿verdad? Conseguimos nuestra condición de base para nuestra recursión 🙂

  = 2 * (2 * (2 * (2 * 2))) = 2 * (2 * (2 * 4)) = 2 * (2 * 8) = 2 * 16 = 32 

Muy bien, vamos a ponerlo en práctica.

 >>> def power(base, exponent): ... # Base condition, if `exponent` is lesser than or equal to 1, return `base` ... if exponent <= 1: ... return base ... ... return base * power(base, exponent - 1) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81 

De acuerdo, ¿cómo se definirá la versión optimizada de Tail Call? Permite pasar el resultado actual como el parámetro a la función en sí y devolver el resultado cuando se cumple la condición base. Mantengámoslo simple y utilicemos el enfoque del parámetro predeterminado directamente.

 >>> def power(base, exponent, result=1): ... # Since we start with `1`, base condition would be exponent reaching 0 ... if exponent <= 0: ... return result ... ... return power(base, exponent - 1, result * base) ... >>> power(2, 5) 32 >>> power(5, 2) 25 >>> power(3, 4) 81 

Ahora, reducimos el valor de exponent en cada llamada recursiva y el result múltiple con base y lo pasamos a la llamada de power recursiva. Comenzamos con el valor 1 , porque estamos abordando el problema a la inversa. La recursión sucederá así.

 power(2, 5, 1) = power(2, 4, 1 * 2) = power(2, 4, 2) = power(2, 3, 2 * 2) = power(2, 3, 4) = power(2, 2, 4 * 2) = power(2, 2, 8) = power(2, 1, 8 * 2) = power(2, 1, 16) = power(2, 0, 16 * 2) = power(2, 0, 32) 

Como el exponent convierte en cero, la condición base se cumple y el result se devolverá, por lo que obtenemos 32 🙂

La salida temprana es típica para funciones recursivas. seq es falso cuando está vacío (por lo tanto, cuando no hay números que quedan por sumr).

La syntax de división permite pasar la secuencia a una función llamada recursivamente sin que se consum un entero en el paso actual.

 def listSum(seq): if not seq: return 0 return seq[0] + listSum(seq[1:]) print listSum([1,3,4,5,6]) # prints 19 
 def listSum(L): """Returns a sum of integers for a list containing integers. input: list of integers output: listSum returns a sum of all the integers in L. """ if L == []: return [] if len(L) == 1: return L[0] else: return L[0] + listSum(L[1:]) print listSum([1, 3, 4, 5, 6]) print listSum([]) print listSum([8]) 
 def power(a,b): #a^b if b==0: return 1 elif b>0: return a * power(a,b-1) elif b<0: return power(a, b+1)/a 

Otra version:

 def listSum(ls): ls_len = len(ls) # Base condition if ls_len==1: return ls[0] if ls_len==0: return None # ls = listSum(ls[0:i]) + listSum(ls[i:]) elif ls_len%2==0: i = int(ls_len/2) return listSum(ls[0:i]) + listSum(ls[i:]) else: i = int((ls_len-1)/2) return listSum(ls[0:i]) + listSum(ls[i:]) 

Siga el ejemplo de @ thefourtheye, podemos decir:

 listSum([1, 3, 4, 5, 6]) = listSum([1, 3]) + listSum([4, 5, 6]) = (listSum([1]) + listSum([3])) + (listSum([4]) + listSum([5, 6])) = (listSum([1]) + listSum([3])) + (listSum([4]) + (listSum([5]) + listSum([6]))) 

Condición básica: cuando ls solo tiene un elemento, devuelve este valor.

 def listsum(list): if len(list) == 1: return list[0] else: return list[0] + listsum(list[1:]) print(listsum([1,5,9,10,20])) 

La idea básica detrás de esta función recursiva es que queremos comprobar si tenemos un caso base que se muestra como if len(list) == 1: Para el caso base, simplemente devolvemos el valor en la lista de return list[0] , de lo contrario, todavía tenemos varios elementos en la lista. En la instrucción else: agregaremos el primer elemento de la lista que es la list[0] al rest de los elementos de la lista. Esto se muestra llamando a la función recursivamente con la lista más corta por 1 elemento: el elemento en index 0– listsum(list[1:]) , este proceso se repite con la lista cada vez más pequeña hasta que llega al caso base, una lista de longitud 1 y luego obtendrá un resultado final.