Recursividad
Para Deitel & Deitel en su libro Como programar en C/C++ una función recursiva es:
“Una función recursiva es una función que se llama así misma, ya sea directa, o indirecta a través de otra función.”
Así que, cuando resolvemos un problema usando una función que se llama a si misma, estamos resolviendo el problema de forma recursiva o usando la recursividad.
El truco con la recursividad es dividir o descomponer el problema en versiones mas pequeñas o manejables del mismo para volver a alimentar a la función, hasta el punto en el que llegamos al caso mas simple o condición de parada que rompe la recursividad y empieza la devolución de resultados hacia arriba.
La recursividad puede usarse en lugar de la iteratividad, que quiere decir, resolver el problema haciendo uso de ciclos, como for y while. El usar el método recursivo o el iterativo dependerá completamente del problema a resolver, puesto que algunos problemas se resuelven de forma más sencilla de forma iterativa y otros se resolverán mas fácilmente de forma recursiva.
Recursividad simple
Comencemos con un clásico de la recursividad… el calculo del factorial!
La Wikipedia dice:
El factorial de un entero positivo n, el factorial de n o n factorial se define en principio como el producto de todos los números enteros positivos desde 1 (es decir, los números naturales) hasta n.
Entonces el factorial de 5 o 5!, por ejemplo, será:
5! = 5*4*3*2*1 = 120
Llevando esto a código, de forma recursiva, nos queda:
Para plantear la recursividad usamos la propiedad del factorial que reza que el factorial de un numero n es igual al factorial de n-1 por n, es decir:
5! = 5 * 4!
y de forma general:
n! = n * (n-1)!
Hacerlo de forma iterativa sería:
Observemos que en este caso la forma iterativa toma 5 lineas de código y la forma recursiva solo toma 2.
Otra cosa que podemos notar en este y en todos los algoritmos recursivos es que debe existir una condición de parada. Como lo mencionamos antes, la condición de parada es el caso mas simple que no necesita calculo ya que su solución es directa. Esta instrucción rompe la recursividad y empieza el proceso de devolución de resultados por parte de las llamadas sucesivas de la función. En el caso del algoritmo que nos atañe la condición de parada esta representada en la instrucción de la linea 15 del código recursivo.
Ejercicios
1.- Escribir un programa que calcule el máximo común divisor (MCD) de dos enteros positivos.
Si M >= N una función recursiva para MCD es:
- MCD = M si N = 0
- MCD = MCD (N, M mod N ) si N <> 0
El programa le debe permitir al usuario ingresar los valores para M y N desde la consola. Una función recursiva es entonces llamada para calcular el MCD. El programa entonces imprime el valor para el MCD. Si el usuario ingresa un valor para M que es menor que N el programa es responsable de intercambiar los valores.
2.- Codifique un programa que calcule la potencia para números enteros de forma recursiva.
