5. Recursión

5.1. factorial

La función factorial es muy usada en probabilidad y estadística. El factorial de n se expresa como n! y esta definido para enteros no negativos como:

$$n! = n \cdot (n - 1) \cdot (n - 2) \cdots 3 \cdot 2 \cdot 1$$

Por ejemplo \(6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\)

De manera Matemática el factorial se define como:

$$ n! = \Biggl \lbrace{ 1, \text{ si } n = 0 \atop n \cdot (n -1)!, \text{ si } n > 0}$$

La definición es recursiva dado que la función ! es usada en la definición de !.

def factorial(n):
    """
    Computes n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
    :param n: nonnnegative integer
    :return: n!
    """
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)


if __name__ == '__main__':
    print('0! = {}'.format(factorial(0)))
    print('4! = {}'.format(factorial(4)))
    print('6! = {}'.format(factorial(6)))
    print('10! = {}'.format(factorial(10)))

Una función recursiva correcta se basa en cuatro cosas:

• La función se debe llamar a sí misma en su definición. Caso recursivo.
• La función no debe llamarse a sí misma en su definición. Caso base.
• Una condición selecciona entre el caso recursivo y el caso base, basándose en al menos uno de los parámetros de la función.
• La ejecución de la función recursiva debe converger al caso base.

Como se calcularía el factorial de manera no recursiva?:

Resultado

def factorial_iterativo(n):
    """ Computes n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
    :param n: nonnegative integer
    :return: n!
    """
    product = 1
    for i in range(n, 0, -1):
        product *= i
    return product

5.2. Sucesión de fibonacci

La sucesión de fibonacci es una secuencia de enteros que comienza con 1, 1 y los elementos subsecuentes son la suma de los dos anteriores.

$$ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 \cdots$$

Un problema común es encontrar el n-ésimo termino de la sucesión.

def fibonacci(n):
    """
    Return the nth Fibonacci number
    :param n: index in the Fibonacci sequence
    :return: the nth Fibonacci number
    """
    if n <= 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


if __name__ == '__main__':
    print('f(1) = {}'.format(fibonacci(1)))
    print('f(5) = {}'.format(fibonacci(5)))
    print([fibonacci(i) for i in range(1, 20)])

5.3. Suma recursiva

Como se puede observar la recursion sirve para dividir el problema en problemas más pequeños y asi obtener la solución al problema original.

Define una función recursiva que sume los primeros n números naturales:

$$ n + (n-1) + … + 1 $$

Resultado

def sum_to_n(n):
    """
    sum the first n natural numbers
    :param n: index
    :return: n + (n-1) + ... + 1
    """
    if n == 1:
        return 1
    return n + sum_to_n(n-1)


if __name__ == '__main__':
    print('5 + 4 + 3 + 2 + 1 = {}'.format(sum_to_n(5)))

Una definición recursiva de la suma de dos números es la siguiente:

$$ suma(m, n) = \Biggl \lbrace{ m, \text{ si } n = 0 \atop 1 + suma(m, n - 1), \text{ si } n > 0}$$

Resultado

def suma(m, n):
    """
    add two numbers recursively
    :param m: integer
    :param n: integer
    :return: m + n
    """
    if n == 0:
        return m
    return 1 + suma(m, n - 1)