A煤n no tienes acceso a esta clase

Crea una cuenta y contin煤a viendo este curso

Recursividad

18/31
Recursos

Aportes 299

Preguntas 37

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi贸n.

Desconoc铆a totalmente que Python tuviera un l铆mite de recursividad. Para conocerlo hay que importar la librer铆a sys:

>>> import sys
>>> print(sys.getrecursionlimit())
1000

Para modificar ese l铆mite

sys.setrecursionlimit(n) # n es el nuevo l铆mite a establecer

https://www.geeksforgeeks.org/python-sys-setrecursionlimit-method/

Nada mejor que aprovechar la cuarentena para aprender en modo 鈥渢urbo鈥 馃槃

鈥淓l l铆mite por omisi贸n es de 1000 llamadas recursivas. Es posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys.setrecursionlimit(n). Sin embargo, si se est谩 alcanzando este l铆mite suele ser una buena idea pensar si realmente el algoritmo recursivo es el que mejor resuelve el problema.鈥

Uniwebsidad
https://uniwebsidad.com/libros/algoritmos-python/capitulo-18/limitaciones

Les comparto un video resumen que hice sobre recursividad, muy bueno para complementar
.
https://drive.google.com/file/d/1xgGFoATJRF9cxsQEueWSViB2FQ8_9sa-/view?usp=sharing
.
V茅anlo y me comparten lo que piensan

Los algoritmos recursivos deben obedecer tres leyes importantes:

Un algoritmo recursivo debe tener un caso base.
Un algoritmo recursivo debe cambiar su estado y moverse hacia el caso base.
Un algoritmo recursivo debe llamarse a s铆 mismo, recursivamente.

RESUMEN: Recursividad


Algoritmica:


Una foma de usar el principio 鈥渄ivide and conquer鈥, definirla as铆 es una forma de crear soluciones a partir de versiones m谩s peque帽as del mismo problema.
Existen soluciones base que permiten iterarse para encontrar un soluci贸n.

Program谩tica:


Una t茅cnica mediante la cual una funci贸n se llama as铆 misma. Una funci贸n adentro de otra funci贸n, existen varios ejemplos de esto.
Los factoriales, la serie de fibonnaci, los fractales.
Podemos definir la recursi贸n como una iteraci贸n, cualquier funci贸n recursiva podemos representarla como un loop.

  1. Siempre escribimos nuestro caso base.
    nota: en python se llega a un l铆mite de recursividad. 驴Cual es el l铆mite?
    El l铆mite de recursividad existe con el fin de que no exista un 鈥淪tack overflow鈥, un flujo excesivo de recursiones causa este famosso problema.
    Sin embargo aunque puede ser peligroso el StackFrames de python puede ser grande.

Python no es un lenguaje funcional y las recursiones de colas no son particularmente una t茅cnica eficiente, reescribir el algotimo iterativamente, de ser posible es generalmente una mejor idea

  • La idea anterior quedar谩 a debate.

Lo que est谩 ocurriendo con la recursi贸n es:
Estamos poniendo stack encima cada ve que ejecutamos un factorial.
Al tener caso base se regresan todos lo valores en una sola l铆na.

El factorial lo que hace es que me ejecuta la funci贸n n, n veces.

A continuaci贸n dejo el estudio comentariado y referenciado de recursividad y su l铆mite.

def me():
    """
鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲 INICIO
        Este c贸digo teiene como prop贸sito Encontrar el l铆mite de recursi贸n te贸rico de mi m谩quina y compararlo con el real.
        1. Defino una funcion recursiva
        2. Le paso dos  argumentos n y resultado_suma  haciendo referencia a un n煤mero n y mi suma.
        3. Imprimo el resultado de suma iterado despu茅s de pasarlo por un ciclo for

鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲  FINAL
            El resultado que me va a devolver al final es:
=>
    [Previous line repeated 993 more times]==> Cuando mi l铆mite de recursi贸n te贸rico es de 1000
        ...
    RecursionError: maximum recursion depth exceeded while calling a Python object
鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲 RECURSION LIMIT
    Para cambiar el l铆mite de recursi贸n en python se usa la funci贸n: sys.setrecursionlimit(limit)
        Esta funci贸n ajusta mi limite m谩ximo de profundidad del stack del interprete de pyhton, este l铆mite previene que la recursi贸n "
        infinita" crashee el "C stack" de Pyhton
鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲 CONSIDERACIONES
    El l铆mite es directamente proporcional a la m谩quina. Es plataforma dependiente y es mejor usarlo cuando el contexto lo amerite.
        Si el nuevo l铆mite de profundidad en la recursi贸n es muy bajo el error RecursionError aparece.

https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲鈻犫枲 驴CUAL ES MI L脥MITE DE RECURSI脫N?
=>      Para saber el l铆mite de recursi贸n se usa: sys.getrecursionlimit()
        Me devuelve el valor actual del limite de recursi贸n para el stack de python.

    """
    pass

#Con este import traigo palabra reservada sys. del sistema
import sys

print(help(me))
print(f'Mi l铆mite de recursi贸n te贸rico es: {sys.getrecursionlimit()}')

if __name__ == '__main__':

    def recursive_function  (n , resultado_sum):
        if n < 1:
            print(f'Vuelve siempre cero para que se ejecute un true infinito {n}. Soy el resultado de una suma y tengo el valor de: {resultado_sum} ')
            return sum
        else:
            # Soy la suma inicialmente de la forma =>  n = n+1
            # Y mi resultado lo voy a iterar, repetir como una suma =>  (n + 1) + resultado_suma
            recursive_function(n - 1, resultado_sum + n)

#El valor de c me dar谩 indicaci贸n de que empieza
    c = 0
# Le digo que me itere hasta 998.
for i in range(998):
    c += 1
    valor_iterado = recursive_function(c, 0)

Se puede cambiar el limite de recursividad importando sys y llamando la funci贸n setrecursionlimit()

import sys
sys.setrecursionlimit(2000)

Limite seg煤n la herramienta:
Colab de google: 972
Pycharm: 998
Visual Studio Code: 998

Esta es la forma en la que puedes modificar el limite de recursion en python para que la funcion pueda llamarse a si misma mas de 1.000 veces.
(esto cambia dependiendo del lenguaje

# Importamos el modulo sys que nos permitira modificar la recursion
import sys

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

        n int > 0
        returns n!
    """
    print(n)
    if n == 1:
        return 1
    
    return n * factorial(n - 1)

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

# Imprimimos el limite de recursion que trae python por defecto con la funcion sys.getrecursionlimit() que trae el modulo sys. 
print(sys.getrecursionlimit())

# Modificamos el limite de recursion a 2000 con la funcion sys.setrecursionlimit() que trae el modulo sys
sys.setrecursionlimit(2000)

print(factorial(n))

Les comparto algo interesante que encontre en un libro.
Las funciones con llamadas recursivas utilizan memoria extra en las llamadas; existe un l铆mite en las llamadas; existe un l铆mite en las llamadas, que depende de la memoria de la computadora. En caso de superar este l铆mite ocurre un error de desbordamiento (overflow).
Complementa un poco lo que mencion贸 el profesor en el video.

El l铆mite del stack de llamadas a funciones en Python es de 999, al tener 1000 en el stack crashea, esto es debido a que Python tiene un l铆mite establecido para evitar el famoso 鈥淪tack Overflow鈥, y tambi茅n evitar recursiones infinitas, a煤n as铆, podemos cambiarlo con:

sys.setrecursionlimit(limite_de_recursiones)

RECURSIVIDAD

La recursividad es una t茅cnica de programaci贸n que nos permite que un bloque de instrucciones se ejecute n veces. Reemplaza en ocasiones a estructuras repetitivas.

La recursividad es un concepto dif铆cil de entender en principio, pero luego de analizar diferentes problemas aparecen puntos comunes.

  1. En Python las funciones o m茅todos pueden llamarse a s铆 mismos. Si dentro de una funci贸n o m茅todo existe la llamada 鈥渁 s铆 mismo鈥 decimos que la funci贸n o m茅todo es recursivo.

  2. Cuando una funci贸n o m茅todo se llama a s铆 mismo, se asigna espacio en la pila para las nuevas variables locales y par谩metros.

驴Qu茅 importancia tiene la recursi贸n en la programaci贸n?

Quiz谩s se quiera dividir un problema complejo en varios problemas peque帽os (Dividir y conquistar). Si ya se est谩 familiarizado con los ciclos e iteraciones, en algunos casos, la recursi贸n puede ser una mejor soluci贸n.

Limitaciones de la Recursi贸n en Python
Cada vez que una funci贸n se llama a si misma ocupa memoria. Por lo tanto, una funci贸n recursiva, puede ocupar mucha mas memoria que una funci贸n tradicional. Python detiene la ejecuci贸n de las funciones luego de que exceden las 1000 ejecuciones. Si se ejecuta el siguiente ejemplo:

Se obtendr铆a el siguiente error:

En otros lenguajes, el programa simplemente fallar铆a. Esto se puede resolver simplemente modificando el l铆mite de recursiones:

Existe una forma de hacer nuestra recursividad mas eficiente, se llama "Tail Recursion"
y es super interesante les dejo el link
https://www.youtube.com/watch?v=_JtPhF8MshA

Una ligera pulida al codigo:

Para 996 ya no lo calcula

RecursionError: maximum recursion depth exceeded while calling a Python object

Hola que tal quiero compartir una pagina que me ayudo a comprender la recursividad en este programa , ya que nos muestra los frames que se van generando y el valor que regresan . Les dejo el link http://www.pythontutor.com/visualize.html#mode=display y una captura de la interfaz.

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n -2)

fibonacci = fib(8)
print(fibonacci)

mi limite es 996.
sys.setrecursionlimit() se utiliza para establecer la profundidad m谩xima de la pila de int茅rpretes de Python en el l铆mite requerido. Este l铆mite evita que cualquier programa entre en una recursi贸n infinita, que conduciria al desbordamiento de la pila C y bloquear谩 el Python.

驴C贸mo funciona el return dentro de este algoritmo?

Lo har茅 con un ejemplo de n = 3 para no hacerlo tan largo:

  1. Insertan n = 3
  2. funcion(3) -> Primer return = 3 * funcion(3 - 1)
    Primer return se queda a la espera de una respuesta de funcion(3 - 1)
  3. funcion(3 - 1) -> Segundo return = 2 * funcion(2 - 1)
    Segundo return se queda a la espera de una respuesta de funcion(2 - 1)
  4. funcion(2 - 1) -> Tercer return = 1
    Por la condicional if que le da el valor de 1 sin llamar a otra funci贸n
  5. Resuelve segundo return = 2 * funcion(2 - 1) = 2 * 1 = 2
  6. resuelve primer return = 3 * funcion(3 - 1) = 3 * 2 = 6
  7. Muestra resultado cuando n = 3 utilizando print(funcion(n)) = 6

La recursi贸n tambi茅n puede ser indirecta: una primera funci贸n llama a una segunda, y est谩 segunda llama a la primera, ejemplo:

def is_even(x):
  if x == 0:
    return True
  else:
    return is_odd(x-1)

def is_odd(x):
  return not is_even(x)

print(is_odd(17))
print(is_even(23))

Python solo calcula hasta 995 en 996 aparece un error

Pas茅 por la universidad y hasta ahora caigo en cuenta que los factoriales son el mejor ejemplo para recursividad, me encanta!

def factorial(i):
    if i == 1 or i == 0: 
        return 1
    elif type(i) == float or i < 0:
        return 'Error, debe ser un n煤mero entero positivo'
    elif i > 1:
        return i * factorial(i-1)

Agreg煤e que si el valor de entrada es 0, tambien deba ser 1 el resultado (por convenci贸n) y que si se tratada de un n煤mero negativo o decimal arroje dicho mismo mensaje.

Es 996. 馃槂 Usen el c贸digo que nos ense帽o el profesor y 995 es el 煤ltimo n煤mero que alcanza la recursividad, 996 ya no lo puede hacer, hasta les manda un mensaje.

Verlo de esta manera me ayud贸 a entenderlo! (obvio est谩 mal escrito en python pero el punto ac谩 fue visualizar lo que estaba pasando)
ahora ac谩 con los valores del ejemplo:

No se si me pasa a mi pero cuando escribo en papel algo que no entiendo, lo comprendo mejor. creo que me toca conseguir un tablero. ejjejee

Para aprender qu茅 es recursividad primero tienes que aprender que es recursividad.

Una buena pr谩ctica es poner siempre un doc string, para hacernos pensar acerca de lo que hace nuestra funci贸n o c贸digo.

A modo de curiosidad y complemento, la palabra RECURSIVIDAD viene del lat铆n y significa 鈥**Cualidad de repetirse indefinidamente que presentan algunos hecho**s鈥

Sus componentes son:
Re- (Hacia atr谩s)
Cursus (Carrera)
Ivus (Relaci贸n activa o pasiva)
-dad (Cualidad de)

Fuente: http://etimologias.dechile.net/ (P谩gina excelente para comprobar la etimolog铆a de cualquier palabra en el idioma espa帽ol)

Seg煤n entiendo el l铆mite por defecto es de 1000 llamadas recursivsas. Sin embargo el l铆mite se puede modificar con sys.serecursionlimit(<limiteDeseado>)

El numero limite en mi caso es de 995, poniendo mas que eso me sale error. RecursionError: maximum recursion depth exceeded while calling a Python object

El l铆mite por omisi贸n es de 1000 llamadas recursivas. Es posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys.setrecursionlimit(n). Sin embargo, si se est谩 alcanzando este l铆mite suele ser una buena idea pensar si realmente el algoritmo recursivo es el que mejor resuelve el problema.

Me parece que este es un buen ejemplo de recursividad.

def jugar(intento = 1):
    respuesta = (input("驴De que color es la naranja? "))
    if respuesta != "Naranja":
        if intento < 3:
            print("Fallaste intentalo de nuevo")
            intento += 1
            jugar(intento)
        else:
            print ("Perdiste")
    else:
        print("Muy bien haz ganado ")
jugar ()

la recursividad ocupa mucha memoria??

Pens茅 resolverlo al rev茅s, dejando al final el caso base:

Si creamos una funci贸n sin caso base, obtendremos el equivalente recursivo de un bucle infinito. Sin embargo, como cada llamada recursiva agrega un elemento a la pila de llamadas a funciones y la memoria de nuestras computadoras no es infinita, el ciclo deber谩 terminarse cuando se agote la memoria disponible.

En particular, en Python, para evitar que la memoria se termine, la pila de ejecuci贸n de funciones tiene un l铆mite. Es decir, que si se ejecuta un c贸digo como el que sigue:

def inutil(n):
return inutil(n-1)

El l铆mite por omisi贸n es de 1000 llamadas recursivas. Es posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys.setrecursionlimit(n). Sin embargo, si se est谩 alcanzando este l铆mite suele ser una buena idea pensar si realmente el algoritmo recursivo es el que mejor resuelve el problema.

Coparto este dato acerca de como modificar la recursividad en python:

鈥淓s posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys. setrecursionlimit(n) . Sin embargo, si se est谩 alcanzando este l铆mite suele ser una buena idea pensar si realmente el algoritmo recursivo es el que mejor resuelve el problema.鈥

Font: https://uniwebsidad.com/libros/algoritmos-python/capitulo-18/limitaciones#:~:text=Es posible modificar el tama帽o,que mejor resuelve el problema.

Les aporto mi c贸digo para calcular el factorial:

def factorial(mi_numero):
""" Calcula el factorial de un n煤mero x 鈥溾"
""" Recibe el n煤mero entero al que se le desea calcular el facturial 鈥溾"
""" Imprime el valor factorial para el n煤mero indicado"""

mi_indice = 1
mi_factorial = 1

while mi_indice <= mi_numero :
mi_factorial = mi_factorial * mi_indice
mi_indice = mi_indice + 1

print('El factorial de: 鈥 + str(mi_numero) + 鈥 es: 鈥 + str(mi_factorial))

def run():
mi_numero = int(input('Digite un n煤mero para calcular el factorial: '))
factorial(mi_numero)

if name == 鈥main鈥:
run()

Excelente explicacion y se complementa muy bien con esta: https://platzi.com/clases/1450-programacion-estructurada/16481-recursividad/

Les comparto mis apuntes de esta Clase:

Se puede definir de dos formas:

  • <h5>Algor铆tmica</h5>

    Una forma de crear soluciones utilizando el principio de 鈥渄ivide y vencer谩s鈥.

  • <h5>Program谩tica</h5>

    Un t茅cnica program谩tica mediante la cual una funci贸n se llama a s铆 misma.

馃泩 Nota: es bueno escribir escribir el docstring de una funci贸n antes de crearla pues as铆 se puede pensar detenidamente en el funcionamiento de la funci贸n.

En Python existe en l铆mite de recursividad. Para conocerlo se usa la librer铆a sys:

import sys
print(sys.getrecursionlimit())

Por defecto el l铆mite de la recursividad son mil ejecuciones de la funci贸n recursiva.

Si se quiere quiere modificar dicho l铆mite:

sys.setrecursionlimit(n)

Siempre escriban su docstring, siempre escriban su especificaci贸n antes de empezar a escribir c贸digo, porque esto les va hacer pensar que es lo que quieren hacer con este c贸digo.

Les comparto dos soluciones para calcular el factorial de manera recursiva:

def recur(n):
    """calcula el factorial del parametro recursivamente
        n int cualquier numero entero
        returns el factorial de n
        """
    if n ==1:
        return n*n
    else:
        return n * recur(n-1)

print(recur(3))

def recur2(n):
    """calcula el factorial del parametro recursivamente
        n int cualquier numero entero
        returns el factorial de n
        """
    return n * recur2(n-1) if n > 1 else 1
print(recur2(3))

Por que Python tiene limite de recursividad?

  • Cada llamada recursiva crea un nuevo espacio en memoria y un nuevo elemento en un stack (pila).

  • Cuando se llega al caso base, cada elemento del stack inicia a retornar valores hasta llegar al primero creado. all铆 entregar铆a la respuesta.

  • La recursividad de manera algor铆tmica es crear soluciones con el principio de divide y venceras, y de manera program谩tica es una t茅cnica mediante el cual una funci贸n se llama a si misma.
  • Una recursi贸n es una forma de iterar

En recursividad debemos definir nuestro caso base, para evitar un infinite loop

  • En python el l铆mite m谩ximo de llamadas de recursividad es de 1000. Es posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys.setrecursionlimit(n).

Si se quiere cambiar el limite se puede hacer de la siguiente manera

import sys
x=(numero de recursividad limite)
sys.setrecursionlimit(x)

Don鈥檛 forget que鈥
Python es el rey del orden y hay que prestar atenci貌n a la identaci貌n en cada linea de codigo

Yo dejo mi c贸digo en JS 馃槂

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const factorial = (num) => {
    if (num === 1 || num === 0) {
        return 1;
    }

    return num * factorial(num - 1);
}

console.log('Programa para determinar el factorial');
rl.question('Escribe el numero del cual quieres saber su factorial: ', (number) => {
    response = factorial(parseInt(number));
    console.log(`El factorial de ${number} es ${response}`);

    rl.close();
});

Fun fact:
En ingl茅s se llama 鈥楻ecursion鈥, mal traducido muchas veces como 鈥榬ecursi贸n鈥. Lo correcto es 鈥榬ecursividad鈥 馃槢

998 es el l铆mite, para modificar el l铆mite, se debe importar la libreria sys y usar sys.setrecursionlimit(n)

import sys
sys.setrecursionlimit(1100)
n = int(input('Escribe un entero: '))
print(factorial(n))

Cuando me hablan de recursividad siempre pienso en el c谩lculo del determinante de una matriz utilizando cofactores.

L铆mite de 995.

El limite factorial que me permiti贸 fue hasta 998, sin embargo importando la librer铆a sys y la instrucci贸n sys.setrecursionlimit() se pudo aumentar le numero factorial. En mi caso solo llego hasta 3900.

En el caso de mi laptop (medio viejita), s贸lo soport贸 hasta 997!

Y en la terminal no aparecieron las primeras 3 iteraciones (Print de n)

import sys
sys.getrecursionlimit()
>>>1000```

No entiendo por que escribe tantas veces para ejecutar el c贸digo cuando podr铆a apretar el botoncito de play arriba a la derecha

Un consejo que se me qued贸 del curso de algoritmos del profe Ricardo Celis:

Al escribir una funci贸n recursiva, siempre debes escribir primero tu condici贸n de salida

En mi caso seg煤n definici贸n matem谩tica en la primera condici贸n tambi茅n se debe incluir el n==0 dado que tambi茅n es 1.

def factorial(num):
    """Calcula el factorial de num
        n int >0
        return n!
    """
    #tanto el factorial de 0 como de 1 es: 1 
    if num == 0 or num == 1:
        return 1
    else:
        return num * factorial(num - 1)
n煤mero=int(input('Escribe un entero: '))
print(factorial(n煤mero))
def factorial(n):
    """Calcula el Factorial de N
    N Int  > 0
    Return N!
    """
    print(n)
    if n == 1:
        return 1
    return n * factorial (n - 1)

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

print(factorial(n))```

El l铆mite por omisi贸n es de 1000 llamadas recursivas. Es posible modificar el tama帽o m谩ximo de la pila de recursi贸n mediante la instrucci贸n sys.setrecursionlimit(n). Sin embargo, si se est谩 alcanzando este l铆mite suele ser una buena idea pensar si realmente el algoritmo recursivo es el que mejor resuelve el problema.

Important铆simo lo del l铆mite de recursi贸n

import sys 
sys.setrecursionlimit(100)

def factorial(n):
    """ Calcula el factorial de n
    n int > 0 
    return n! """
    if n == 1:
        return 1
    
    return n*factorial(n-1)

n = int(input('Escoja un entero: '))

print(factorial(n))

Limite de recursividad en Python de una funci贸n a ella misma es de 1000 veces

[6:26] Caso base: hasta donde ira nuestra iteraci贸n. En el ejemplo definimos el caso base del factorial como 1! = 1 (en matem谩ticas el caso base del factorial es 0! = 1).

El l铆mite de recursividad en Python, por defecto es de 1000 y se puede cambiar mediante:
sys.setrecursionlimit(n)

Para los que todav铆a no terminaron de entender

def factorial(n):
    # Caso Base para evitar un bucle intinito
    if n == 1:
        return 1 
    
    # definicion matematica
    return n * factorial(n - 1)

Este v铆deo me ense帽o factoriales y la funci贸n al mismo tiempo. brutal
#41 Python Tutorial for Beginners | Factorial using Recursion

En java la recursividad es muy similar a la de Python, tambi茅n se tienen Stacks (pilas), estas son una de las tantas formas de estructuraci贸n de datos que lo que hace es ir apilando a la pila de manera que lo primero que ingresa es lo 煤ltimo que sale (Es como una caja a la que le vamos metiendo libros). En este caso apilamos llamados de funciones, osea鈥 la primera funci贸n que se ejecuta es la 煤ltima que retorna, la 煤ltima funci贸n que se ejecuta es la primera que retorna un valor; En nuestro ejemplo la 煤ltima funci贸n es la del caso base 鈥1鈥.

Mi aporte de la clase 馃挌馃悕鉁嶐煆

no entiendo como da ese resultado, 3 horas de an谩lisis.

Los apuntes para la clase.

Hola a todos 馃枛馃徎 La recursividad ocupa m谩s recursos que un ciclo while o for? 馃

Comparto el codigo del programa pero utilizando lo que se conoce como un punto de entrada y una funci贸n principal, cosa que es buena practica en Python:

def factorial(n):
    """ Calcula el factorial de n.

    n int > 0
    return n!
    """
    print(n)
    if n == 1:
        return 1

    return n * factorial(n-1)

#Funci贸n principal
def main():
    n = int(input('Escribe un entero: '))
    #print('Este es el resultado' + str (factorial(n)))
    print(f'Este es el resultado: {factorial(n)}')

#Entry Point o punto de entrada
if __name__ == '__main__':
    main()

Algoritmo para encontrar el l铆mite de recursividad y con cualquier n煤mero me da 996 iteraciones.
Para modificar el l铆mite se puede utilizar el siguiente m茅todo: sys.setrecursionlimit()

He visto que a mas personas su maximo factorial es el 1000, pero he estado probando yo, y mi maximo factorial es el 994. Si pongo el 995 me salta el error.
Nose si es por mi pc que ya esta vieja o es por el lenguaje

隆no entend铆 nada!

Seg煤n mi computadora el limite de recursividad es de 992

[Previous line repeated 992 more times]
  File "C:\Users\admin\Desktop\Exercices\factorial.py", line 9, in factorial
    print(n)
RecursionError: maximum recursion depth exceeded while calling a Python object   

Basicamente recursividad es invocar a la misma funci贸n dentro de ella para que se repita con el objetivo de iterar alguna variable y obtener alg煤n resultado.

驴Porque hasta ahora no sab铆a que pod铆a hacer un loop mediante recursividad? Me hubiera ahorrado mucho tiempo!

hice la prueba y a partir de 999 Python ya no puede ejecutar el comando

Les comparto mis apuntes de la clase
Apuntes

Les recomiendo ver este video para complementar
https://www.youtube.com/watch?v=yX5kR63Dpdw

def factorial(n):
    """ Calcula el factorial de n.

    n int > 0
    returns n!
    """
    print(n)
    if n == 1:
        return 1

    return n * factorial(n - 1)
n = int(input('Escribe un entero: '))

print(factorial(n))

Recursividad

Algoritmica: una forma de crear soluciones utilizando el principio de 鈥渄ivide y vencer谩s.鈥

Program谩tica: Una t茅cnica program谩tica mediante la cual una funci贸n se llama a si misma.

Una peque帽a observaci贸n matem谩tica, de la misma formula de recurrencia n! = n * (n-1)!
si despejamos:
(n-1)! = n! / n
y, a n, le damos el valor de n = 1
obtenemos:
(0)! = 1! / 1 = 1
Es decir 0! = 1

Amo estas clases

Para el que no lo entendi贸:

La funci贸n factorial se vuelve a llamar a si misma dentro pero rest谩ndole un 1 al numero que le lleg贸 por par谩metro, hasta que N sea 0, en ese caso va a devolver el resultado de haber multiplicado a n * (n - 1) hasta que n sea 1.
Resumidamente la funci贸n se llama a si misma.

Busqueda binaria con recursividad, usando los 100 primeros n煤meros de la serie de Fibonacci

def fibo(num):
   """lISTA LOS NUMEROS DE 
      LA SERIE DE FIBONACCI
   """
   fibos = [0,1,1]

   for i in range(num-2):
      tope = len(fibos)-1
      fibos.append(fibos[tope-1]+fibos[tope])
   return fibos


def binary_search(sort_list, left, rigth, target): 
   if left > rigth:
      return False
   index = (left+rigth)//2
   value = sort_list[index]
   if value == target:
      return True
   elif value < target:      
      return binary_search(sort_list, index+1, rigth, target)
   else:
      return binary_search(sort_list, left, index-1, target)


def run():
   nums = fibo(100)
   last = len(nums)-1
   target = int(input("Ingresa un numero: "))
   flag = binary_search(nums, 0, last ,target)
   if flag:
      print(f'El n煤mero {target} pertene a la serie de Fibonacci')
   else:
      print(f'El n煤mero no {target} pertene a la serie de Fibonacci')

wow

Le hice una peque帽a mejorita ya que si ingresamos 0 o 1el factorial sera 1

def factorial(n):
"""
	Calcula el factorial de n
	n int > 0
  	return n!
"""
    print(n)
    if n == 0 or n ==1:
        return 1
    else:
        return n * factorial(n-1)

En realidad el l铆mite ser铆a llegar a 0!, que es 1. Aunque esto no s茅 si nos llevar铆a a alg煤n error en la ejecuci贸n del c贸digo. Aqu铆 dejo un video al respecto, de Derivando (YouTube): https://www.youtube.com/watch?v=Q0S8pl4y4B8

Qued茅 sorprendido, pens茅 que 铆bamos a hacer uso de un ciclo o loop. 馃槻

En la ciencias de la computaci贸n, la recursividad es muy importante y es una forma para solventar problemas. De hecho, recursi贸n es una de las ideas centrales de ciencia de computaci贸n. de hecho resolver un problema mediante recursi贸n significa que la soluci贸n depende de las soluciones de peque帽as instancias del mismo problema.2鈥

Consejos para aplicar recursividad a cualquier problema
Algo que puede ser de mucha ayuda a la hora de pensar en recursividad es lo siguiente:

Cuando tratamos un problema con recursividad, debemos pensar en dos cosas:

  • Un caso recursivo (o la parte recursiva): que es la acci贸n o serie de pasos o acciones que se van a repetir constantemente. En el caso del factorial, la parte recursiva ser铆a multiplicar el par谩metro actual (n) por la funci贸n factorial del n煤mero menos 1 (factorial(n-1)).

  • Un caso base (o caso de parada): que es el valor m铆nimo o lo que debe suceder para que acabe la recursividad. Esta parte es muy importante para que la funci贸n se ejecute de manera correcta y no se termine cayendo en un infinite loop (o ciclo infinito)

Un consejo personal que me ha servido mucho es siempre intentar pensar primero en el caso de parada, ya que suele ser la parte crucial. Sin embargo esto depende mucho del problema y de como se implementa la recursividad.
Tambi茅n es 煤til imaginarse que peque帽o problema debo resolver primero para estar m谩s cerca de la soluci贸n (esto me dar铆a un indicio de la_ parte recursiva_), y como quedar铆a finalmente mi variable o variables, una vez que llegu茅 a la soluci贸n (esto me indicar铆a el caso de parada)
隆Espero les sea de ayuda!

Las funciones recursivas son funciones que se llaman a s铆 mismas durante su propia ejecuci贸n. Ellas funcionan de forma similar a las iteraciones, pero debe encargarse de planificar el momento en que dejan de llamarse a s铆 mismas o tendr谩 una funci贸n recursiva infinita.

Estas funciones se estilan utilizar para dividir una tarea en sub-tareas m谩s simples de forma que sea m谩s f谩cil abordar el problema y solucionarlo.

si importamos sys, no solo que podemos ver el limite de recursividad sino que poniendo sys.exit terminamos con la ejecucion del programa.

Como han dicho por alli , si asi es

import sys
print(sys.getrecursionlimit())

ya entendi perfecto por que el if n == 1: return 1 si alguien no entiende se lo explico con lujo de detalle

Este es mi codigo, en uno us茅 el ciclo While, adem谩s de agregarle el caso n=0 y n<0.
Espero que se entienda.

def factorialWhile(n):
    """
    Calcula el factorial de un numero, usando ciclo While. 

    """

    if n < 0:
        print("Ingresa un numero positivo")
    else:
        cont = 1
        acumulador = 1

        while cont <= n:
            acumulador *= cont
            cont += 1 

    return acumulador

def factorial(n):
    """
    Calcula el factorial de un numero, usando ciclo Recursividad. 
    """

    if n < 0 :
        print("Ingresa un numero positivo!!!")

    else:  
   
        if n == 0:
            return 1
    
        if n == 1 :
            return 1
    
        else :
            return n * factorial(n - 1)
        


def run():
    numero = int( input("Ingresa un numero: ") )
    print("El factorial de " + str(numero) + " es: " + str(factorial(numero)))
    print("El factorial de " + str(numero) + " es: " + str(factorialWhile(numero)))



if __name__ == "__main__":
    run()

No sobra decir que la recursividad puede tener dos formas de implementaci贸n:

  • Recursividad por pila.
  • Recursividad por cola.

El ejemplo visto en esta clase es una recursividad por pila: Por cada llamado recursivo se deja una operaci贸n pendiente por realizar y solo cuando llega al caso base, se empieza a finalizar esas operaciones pendientes y as铆 obtener el resultado final.

La implementaci贸n anterior, tiene un costo alto en rendimiento para n煤meros grandes, en el caso del factorial. Ac谩 es donde entra en acci贸n la recursividad por cola. Su diferencia con la otra implementaci贸n es, no dejar operaciones pendientes en cada llamado recursivo, sino que vaya calculando el resultado final y cuando llegue al caso base, ya tienes la respuesta final a tu problema. Ejemplo para el caso de factorial:

def factorial_extendido(n, result):
    if (n == 0):
        return result
    else:
        return factorial_extendido(n - 1, n * result)


def factorial_recursivo_cola(n):
    return factorial_extendido(n, 1)


n = int(input('Escribe un n煤mero entero: '))

print(factorial_recursivo_cola(n))

Esto casi no lo hablan cuando explican recursividad y me pareci贸 bueno compartirlo.