fuente: http://www.etnassoft.com/biblioteca/introduccion-al-desarrollo-de-software/, http://es.wikipedia.org/wiki/Sucesi%C3%B3n_de_Fibonacci y producción propia Funciones recursivas En el cuerpo de la función se puede realizar una llamada a la misma. Esta llamada se denomina llamada recursiva, ya que la definición de la función se hace en términos de ella misma. Este tipo de llamadas no es incorrecto pero hay que vigilar que no se produzcan indefinidamente, es decir, que haya algún caso (llamado paso base) donde el flujo de ejecución de las instrucciones no implique realizar ninguna llamada recursiva y, por otra parte, que la transformación que se aplica a los parámetros de éstas conduzca, en algún momento, a las condiciones de ejecución anterior (que conduzcan al paso base). En particular, no se puede hacer lo siguiente: /* ... */ void menu() { /* mostrar menú de opciones, */ /* ejecutar opción seleccionada */ menu(); /* ... */ La función anterior supone realizar un número indefinido de llamadas a menu() y, por tanto, la continua creación de entornos locales sin su posterior liberación. En esta situación, es posible que el programa no pueda ejecutarse correctamente tras un tiempo por falta de memoria para crear nuevos entornos. Un ejemplo de una función recursiva que termina sería el siguiente: int factorial(int i) { if (i==0 || i==1) return 1; else return i*factorial(i-1); } Al hacer la llamada con el valor 4 por ejemplo se tendría lo siguiente: factorial(4)= 4 * factorial (4-1) = 4 * 3 * factorial (3-1) = 4 * 3 * 2 * factorial (2-1) = 4*3*2*1 Acordarse que para cada llamada recursiva de factorial se debe crear el entorno local de ejecución o sea reservar memoria para las variables locales (no tiene), parámetros formales (tiene al entero i) y para el retorno (es un entero). Por lo que para cada llamada precisamos espacio para dos enteros. Y como no se libera la memoria hasta que se llega al paso base (en este caso i==0 o i==1), si se llamara a factorial con el valor 100 se precisaría espacio para 100 * 2 enteros. Esto hace que la recursión consuma mucha memoria por lo que tiene un límite el factorial que se puede calcular. Además está el límite de la variable int que puede representar sólo de –2.147.483.648 a +2.147.483.647 en un computador de 32 bits. De esta manera vemos que las llamadas a factorial se dejan de hacer cuando el i llega al valor 1 por lo que no se necesita reservar memoria ilimitada para que la función ejecute. Otra función recursiva es la de la Sucesión de Fibonacci: fibonacci(0)=0 fibonacci(1)=1 fibonacci(i) = fibonacci(i-1) + fibonacci(i-2) para i=2,3,4,5,... A diferencia de factorial en Fibonacci se calcula el elemento siguiente de la sucesión a partir de los dos anteriores. Pasado a código C++ quedaría de la siguiente manera: int fibonacci(int i) { switch(i){ case 0: return 0; case 1: return 1; default: return fibonacci(i-1) + fibonacci (i-2); } } Al hacer la llamada con el valor 4 por ejemplo se tendría lo siguiente: fibonacci(4)= fibonacci(3) + fibonacci (2)= fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)= fibonacci(1) + fibonacci(0) + 1 + 1 + 0= 1 + 0 + 2 = 3 Realizar los siguientes ejercicios de manera recursiva: 1.Hacer un programa para determinar el número de dígitos necesarios para representar a un número entero dado. El algoritmo consiste en hacer divisiones enteras por 10 del número hasta que el resultado sea un valor inferior a 10. 2.Se desea calcular el capital final acumulado en una cuenta bancaria sabiendo que el capital inicial es $1000, el interés anual es 5% y se tuvo el dinero depositado durante 8 años. 3.Hacer un programa que te diga si determinada secuencia de caracteres se encuentra en otra secuencia de caracteres. 4.Hallar de manera recursiva el mcd de dos números (tener en cuenta la forma de calcular el mcd dada en el repartido teórico de la clase de “Ámbito de las variables” Recordatorio de accesos directos en IDE Turbo C++: 1.Compilar = Alt + F9 2.Ejecutar = Ctrl + F9 3.Ver resultado = Alt + F5 4.Ejecutar paso a paso = F7 Algunos errores que tira el IDE Turbo C++ y sus soluciones: Error Solución Function X should have prototype Falta la linea #include … que incluya la librería donde esta declarada X Statement missing ; Agregar ; al final de la linea anterior a la del error