Algoritmo recursivo [cálculo factorial]

Algoritmo recursivo [Cálculo factorial]

2024-07-12

algoritmo recursivoes una técnica de programación muy utilizada en informática y matemáticas que permite realizar funcionesdirectooindirectotierrallamarse a sí mismo para resolver el problema.recursivoIdea básicaEs la descomposición de problemas complejos en subproblemas más pequeños y similares hasta que estos subproblemas sean lo suficientemente simples como para resolverse directamente.

Los algoritmos recursivos suelen contener dos partes principales:

Caso base: esta es la condición de terminación para llamadas recursivas, es decir, la instancia de problema más simple que se puede responder directamente sin más llamadas recursivas.
Caso recursivo: este es el proceso de dividir un problema en subproblemas más pequeños y resolver estos subproblemas mediante llamadas recursivas. El caso recursivo debe garantizar que cada llamada avance hacia el caso base.

Pasos del algoritmo recursivo:

Identifique casos base: determine qué problemas se pueden resolver directamente sin más llamadas recursivas.
Diseñar situaciones de recursividad: definir cómo dividir un problema grande en subproblemas más pequeños y cómo combinar las soluciones de los subproblemas para obtener una solución al problema original.
Garantizar la convergencia recursiva: asegúrese de que las llamadas recursivas eventualmente lleguen al caso base y evite la recursividad infinita.

Ventajas y desventajas de los algoritmos recursivos:

ventaja: El código es conciso, la lógica es clara y es fácil de entender y escribir.
defecto : Puede ser menos eficiente que la solución iterativa porque implica una mayor sobrecarga de llamadas a funciones. Además, una recursividad demasiado profunda puede provocar errores de desbordamiento de la pila.

La recursividad tiene aplicaciones en muchos algoritmos, comorecorrido del árbol、Búsqueda gráfica、Programación dinámica, etc. . El uso adecuado de la recursividad puede simplificar la resolución de problemas complejos.

Ejemplo: calcular factorial

def factorial(n):#自定义求n的阶乘函数
        if n==1:#判断n=1
                return 1#返回1结束
        else:#递归条件 即n!=1
                return n*factorial(n-1)#递归求阶乘

number = int(input("请输入一个正整数:"))#输入n的值
result = factorial(number)#调用阶乘函数
print("%d 的阶乘是 %d" %(number,result))#输出结果
1
2
3
4
5
6
7
8
9

Insertar descripción de la imagen aquí

Explicación del código

factorial La función recibe un parámetro. n , representa el número para el cual se va a calcular el factorial.El factorial se expresa comon!, definido como todo menor o igual a n El producto de números enteros positivos. Por ejemplo,5! = 5 × 4 × 3 × 2 × 1 = 120。

Dentro de la función:

Caso base: si n Si es igual a 1, la función devuelve 1 directamente. Esta es la condición de terminación de la recursividad porque el factorial de 1 se define como 1.
Caso recursivo: si n no es igual a 1, la funciónn yfactorial(n-1) Los resultados se multiplican.factorial(n-1) es verdadfactorial funciónLa llamada misma , pero el parámetro se reduce en 1.Este llamado continuará hastan llega a 1.

La clave de la recursividad es que cada llamada recursiva se acerca al caso base, llegando eventualmente al caso base y comenzando a devolver valores. En este ejemplo, cada llamada recursiva disminuye n en 1 hasta que n se convierte en 1.

Aviso:

La recursión puede encontrar problemas de rendimiento o errores de desbordamiento de pila al manejar valores grandes porque cada llamada de función ocupa una parte del espacio de la pila. Para operaciones matemáticas simples como factoriales, suelen existir métodos iterativos más eficientes y fáciles de recordar. Sin embargo, la recursividad proporciona una forma elegante y fácil de entender de resolver ciertos problemas.

Compartir tecnología