Recursibidad Algorítmica

Una forma de crear soluciones utilizando el principio de "divide y vencerás".

Recursibidad Programática

Una técnica programática mediante la cual una función se llama a sí misma.

n! es igual a esta cosa donde:

Símbolo de producto significa que es un loop donde i = 1 que es el contador de ciclos y el ultimo ciclo será n. La i. significa que en cada ciclo el resultado se multiplicara por i.

Se puede aprovechar para hacer un programa que realice factoriales:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ce23d7a2-546c-4ffd-9662-e36230e1c7e9/Untitled.png

En otras palabras i se multiplicara n veces por si misma guardando en ella misma el producto en cada multiplicacion: ej n= 5 5! = 1*1*2*3*4*5

def factorial(numero):
  """Calcula el factorial de numero

  numero int > 0 
  returns n!
  """
  if numero == 1:
    return 1

  return numero * factorial(numero -1)

numero = int(input('Escribe un numero entero: '))

print(factorial(numero))

Recursividad con Fibonacci

Imagina que agregamos el numero 1 Entraría en el if por lo tanto hasta ahí llegaría nuestro programa

Si elegimos el numero 2 Se brinca el if porque pues no cuenta, y se va directo al return que llama directo a la función, por lo que obtenemos el primer atributo del return fibonacci(2 - 1), y como es igual a 1, retornamos el 1. el segundo punto es fibonacci(n - 2) por lo que su respuesta es 0 al volver a la función, pero en la condición vemos que si es 0 retorna un 1. es decir que al momento de retornar tenemos 1 + 1.

Si elegimos el numero 3

Entramos a la función con n=3, por lo que nos brincamos el if, el primer resultado del retorno es fibonacci(3 - 1), es decir que volvemos a entrar la función con fibonacci(2), por lo que nos brincamos el if y nos vamos al return. Espero te hayas dado cuenta, obtenemos el resultado de si hubiéramos elegido el numero dos, si no te queda claro sigue los pasos de arriba donde dice 'si elegimos el numero 2'.

El chiste que de la línea return ya tenemos el primer termino que es 1+1 que es igual a fibonacci(2). Ahora calculamos el otro numero fibonacci(3-2) que seria igual a fibonacci(1) por lo tanto seria igual a 1.

Por si acaso te dire qué está pasando aqui, el return principal se encarga de hacer una lista de sumas de puros digitos 1.

Es decir que tu al buscar el fibonacci de algún numero, el resultado es la suma de 0+1 n veces.

Un ejemplo mas: tu al buscar el fibonacci de 6 su resultado será el return que llamo a la misma función 13 veces sumando 1+1+1+1+1+... hasta obtener 13. Cada iteración sumó un 1 al resultado

Si elegimos el numero 4 Este ejemplo será mas gráfico

fibo(4)
= fibo(4-1) + fibo(4-2)
= fibo(3) + fibo(2)
= (fibo(3-1) + fibo(3-2))  + (fibo(2-1) + fibo(2-2))
= (fibo(2) + fibo(1))  + (fibo(1) + fibo(0))
= ((fibo(2-1) + fibo(2-2)) + fibo(1))  + (fibo(1) + fibo(0))
= ((fibo(1) + fibo(0)) + fibo(1))  + (fibo(1) + fibo(0))
= ((1 + 1) + 1) + (1 + 1))
= 1 + 1 + 1 + 1 + 1
= 5
def fibonacci(n):
  print(n)
  if n == 0 or n == 1:
    return 1
  
	return fibonacci(n - 1) + fibonacci(n - 2)

n = int(input('Ingresa un numero: '))

print(f'El numero final fibonacci es {fibonacci(n)}')