sierpinski - Conceptos básicos de recursión en Python

reglas de recursividad

Question

"Escribe una función recursiva," listSum "que toma una lista de enteros y devuelve la suma 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 hacerlo, ya que no se permiten funciones integradas especiales.

Answer 1

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

La sintaxis de corte permite pasar la secuencia a una función llamada recursivamente sin un número entero consumido 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

Answer 2

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 base: cuando ls solo tiene un elemento, devuelve este valor.

Answer 3

Siempre que se enfrente a un problema como este, intente expresar 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 resto 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 básica de su recursión. Cuando se cumple la condición base, la recursión llegará a su fin. Ahora, intentemos implementarlo.

Lo principal aquí es dividir la lista. Puedes usar slicing 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 llamada de cola

Una vez que comprenda cómo funciona la recursividad anterior, puede intentar mejorarla un poco. Ahora, para encontrar el resultado real, también dependemos del valor de la función anterior. La instrucción return no puede devolver el valor de inmediato hasta que la llamada recursiva devuelva un resultado. Podemos evitar esto pasando la corriente al parámetro de la función, así

>>> 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 suma 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 suma en el parámetro de result , por lo que la devolvemos. Ahora, la última declaración de return tiene listSum(ls[1:], result + ls[0]) , donde agregamos el primer elemento al result actual y lo pasamos nuevamente 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 índice

Ahora, puede pensar que estamos creando tantas listas intermedias. ¿Puedo evitar eso?

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

>>> 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 la función interna

Si observa la definición de la función ahora, le está pasando tres parámetros. Digamos que va a lanzar esta función como API. ¿Será conveniente que los usuarios pasen tres valores cuando realmente encuentren la suma 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, como este

>>> 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 , solo 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 transfiriendo ls a la recursion sino que la estamos usando dentro de ella. Se puede acceder a ls dentro de la recursion debido a la propiedad de cierre.

Versión de parámetros predeterminados

Ahora, si desea mantenerlo simple, sin crear una función interna, puede utilizar 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 será asignado 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 la base elevada al exponent potencia.

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

Ahora, ¿cómo podemos hacer esto de forma recursiva? 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, entonces tenemos la idea. La base multiplicada por sí misma, el tiempo exponent da el resultado. Bien, ¿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? Tenemos nuestra condición base para nuestra recursividad :-)

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

Muy bien, vamos a implementarlo.

>>> 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 la llamada de cola? Pasemos el resultado actual como parámetro a la función misma y devolvamos el resultado cuando cumpla la condición base. Hagámoslo simple y usemos el enfoque de 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 del 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 nos estamos acercando al 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, se cumple la condición base y se devuelve el result , por lo que obtenemos 32 :-)

Answer 4

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

Answer 5

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 verificar si tenemos un caso base que se muestra como if len(list) == 1: Para el caso base, simplemente devolvemos el valor en la lista return list[0] , de lo contrario, todavía tenemos múltiples elementos en la lista. En la declaración else: agregaremos el primer elemento de la lista que es list[0] al resto de los elementos de la lista. Esto se muestra llamando a la función recursivamente con la lista más corta en 1 elemento: el elemento en index 0-- listsum(list[1:]) , este proceso se repite con la lista cada vez más pequeña hasta llegar al caso base: una lista de longitud 1 y luego obtendrá un resultado final.

Answer 6

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