[Utu-emt-prog2-info] clase 4 Funciones recursivas

[Federico Kouyoumdjian]

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