Recursividad en Python

El término Recursión se puede definir como el proceso de definir algo en términos de sí mismo. En palabras simples, es un proceso en el que una función se llama a sí misma directa o indirectamente. Ventajas de usar la recursividad

• Una función complicada se puede dividir en subproblemas más pequeños utilizando la recursividad.
• La creación de secuencias es más simple a través de la recursión que utilizando cualquier iteración anidada.
• Las funciones recursivas hacen que el código parezca simple y efectivo.

Desventajas de usar la recursividad

• Se consume mucha memoria y tiempo a través de llamadas recursivas, lo que hace que su uso sea costoso.
• Las funciones recursivas son difíciles de depurar.
• El razonamiento detrás de la recursividad a veces puede ser difícil de analizar.

Sintaxis:

def func(): <--
              |
              | (recursive call)
              |
    func() ----

Ejemplo 1: Una secuencia de Fibonacci es la secuencia entera de 0, 1, 1, 2, 3, 5, 8…. 

# Program to print the fibonacci series upto n_terms
 
# Recursive function
def recursive_fibonacci(n):
  if n <= 1:
      return n
  else:
      return(recursive_fibonacci(n-1) + recursive_fibonacci(n-2))
 
n_terms = 10
 
# check if the number of terms is valid
if n_terms <= 0:
  print("Invalid input ! Please input a positive value")
else:
  print("Fibonacci series:")
for i in range(n_terms):
    print(recursive_fibonacci(i))

Fibonacci series:
0
1
1
2
3
5
8
13
21
34

Producción:

Fibonacci series:
0
1
1
2
3
5
8
13
21
34

Ejemplo 2: ¡El factorial de 6 se denota como 6! = 1*2*3*4*5*6 = 720. 

# Program to print factorial of a number
# recursively.
 
# Recursive function
def recursive_factorial(n):
  if n == 1:
      return n
  else:
      return n * recursive_factorial(n-1)
 
# user input
num = 6
 
# check if the input is valid or not
if num < 0:
  print("Invalid input ! Please enter a positive number.")
elif num == 0:
  print("Factorial of number 0 is 1")
else:
  print("Factorial of number", num, "=", recursive_factorial(num))

Factorial of number 6 = 720

¿Qué es la recursividad de cola?

Un tipo único de recursividad donde el último procedimiento de una función es una llamada recursiva. La recursividad se puede automatizar realizando la solicitud en el marco de pila actual y devolviendo la salida en lugar de generar un nuevo marco de pila. El compilador puede optimizar la recursión de cola, lo que la hace mejor que las funciones recursivas que no son de cola. ¿Es posible optimizar un programa haciendo uso de una función recursiva de cola en lugar de una función no recursiva de cola?Si consideramos la función dada a continuación para calcular el factorial de n, podemos observar que la función parece una cola recursiva al principio, pero es una función no cola recursiva. Si observamos de cerca, podemos ver que el valor devuelto por Recur_facto(n-1) se usa en Recur_facto(n), por lo que la llamada a Recur_facto(n-1) no es lo último que hace Recur_facto(n). 

# Program to calculate factorial of a number
# using a Non-Tail-Recursive function.
 
# non-tail recursive function
def Recur_facto(n):
   
    if (n == 0):
        return 1
   
    return n * Recur_facto(n-1)
   
# print the result
print(Recur_facto(6))

720

Podemos escribir la función dada Recur_facto como una función recursiva de cola. La idea es usar un argumento más y en el segundo argumento acomodamos el valor del factorial. Cuando n llega a 0, devuelve el valor final del factorial del número deseado. 

# Program to calculate factorial of a number
# using a Tail-Recursive function.
 
# A tail recursive function
def Recur_facto(n, a = 1):
   
    if (n == 0):
        return a
   
    return Recur_facto(n - 1, n * a)
   
# print the result
print(Recur_facto(6))

720