Algoritmo Recursivo
Defina el algoritmo
Es una técnica que permite que una función se llame a si misma. El concepto de Recursividad va ligado a la repetición. Son recursivos aquellosalgoritmo que estando encapsulados dentro de una función, son llamados desde la misma una y otra vez, en contraposición a los algoritmos iterativos que hacen uso de bucles while, do-while, for, etc.
Paraque una función recursiva sea válida, la referencia a si misma debe ser relativamente mas sencilla que el caso considerado.
En un algoritmo recursivo distinguimos 2 partes.
- Caso trivial, baseo fin de recursión: Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a si mismo. Evita la continuación indefinida de las partes recursivas.
- Partepuramente recursiva: Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
Un ejemplo gráfico
Generarel seudocódigo
A manera de ejemplo (típico en la enseñanza de este tema) es el cálculo de factorial de manera recursiva.
Se puede definir el factorial de un número entero positivo x como sigue:x!=x*(x-1)*(x-2)...*3*2*1
donde ! indica la operación unaria de factorial.
Definimos, además:
1!=1 0!=1
Sin embargo, podemos observar que la definición del factorial de un número x, puedeexpresarse, a su vez, a través del factorial de otro número:
x!=x*(x-1)!
Es decir, para conocer el factorial de x basta con conocer el factorial de x-1 y multiplicarlo por x. Para conocer el factorialde x-1 basta con conocer el factorial de x-2, y multiplicarlo por x-1. Este proceso se realiza recursivamente, hasta llegar a la solución trivial, donde necesitamos el factorial de 1, el cual es 1.Lo importante a notar en la igualdad anterior es que expresa un proceso recursivo, donde definimos una operación en términos de sí misma.
El seudocódigo queda así:
inicio de la rutina Factorial...
Regístrate para leer el documento completo.