<< Recurrencia e iteraciones >>

ninguna

Para entender la recursividad,
primero hay que entender la recursividad

La recursividad es algo bastante simple. Es un concepto en algún sentido parecido al de inducción (no sé por qué pero yo los veo parecidos).

Los procesos recursivos son los que se definen en función de sí mismos. La idea es que muy frecuentemente, cuando tenemos que resolver un problema, es bastante fácil mediante alguna operación llevarlo a un caso más simple de él mismo.

Por ejemplo, supongamos que tenemos que calcular n! (n factorial, típico ejemplo de recursividad). Para los que no saben, n! es el producto 1.2.3...n. Una manera de hacerlo es con un bucle del tipo:

Function Factorial(n:LongInt):LongInt;
Var
k,P:LongInt;
Begin
P:=1;
For k:=1 To n do
	P:=P*k;
Factorial:=P;
End;

A esto se le llama un proceso iterativo.

Una solución recursiva del mismo problema sería:

Function Factorial(n:LongInt):LongInt;
Begin
	If n=0 Then Factorial:=1
		 Else Factorial:=n*Factorial(n-1);
End;

Esta solución se basa en el hecho de que n! = n*(n-1)! Cuando n>0.

Noten que si no chequeara inicialmente si n=0, la función se invocaría a sí misma infinitas veces y nunca terminaría de ejecutarse (en realidad en poco tiempo daría error). Por eso, siempre una función recursiva tiene una condición inicial en la que no debe llamarse a sí misma. Esta situación es similar al primer caso de la inducción.

El propósito de la recursión es hacer códigos más simples y fáciles de programar. Con un poco de práctica les aseguro que además son mucho más fáciles de entender.

En el caso del factorial, los dos métodos no consumirán tiempos muy diferentes. Los procesos recursivos suelen ocupar más memoria y tardar un poquito más que los iterativos porque cuando el compilador llama a una subrutina guarda todas las variables locales en una zona de memora llamada "stack".

De todas maneras, los dos procedimientos de arriba se toman un tiempo proporcional a n para ejecutarse. La constante de proporcionalidad es menor en el primero, pero eso no es algo de lo que debamos preocuparnos demasiado porque depende también de la versión de nuestro compilador, de la computadora que usamos, etc.

Veamos otro ejemplo. La famosa sucesión de Fibonacci se define de la siguiente manera:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2) cuando n>2

En este caso, la misma definición del problema es recursiva. Es claro que la forma más fácil de programarlo es recursivamente.

La solución recursiva sería:

Function Fibonacci(n:LongInt):LongInt;
Begin
	if (n=1) or (n=2) Then Fibonacci:=1
	 else Fibonacci:=Fibonacci(n-1)+Fibonacci(n-2);
end;

Una solución iterativa se vería de la siguiente manera:

Function Fibonacci(n:LongInt):LongInt;
Var
a,b,aux,k:LongInt;
Begin
	a:=1;
	b:=1;
	For k:=2 To n do
	begin
		aux:=b;
		b:=a+b;
		a:=aux;
	end;
	Fibonacci:=a;
end;

Este es un mejor ejemplo de cuanto más simple puede ser el uso de técnicas recursivas. En problemas más complicados la diferencia puede ser aún mayor.

La solución iterativa simplemente hace lo que cualquier ser humano haría si tuviera que calcular el número n de la sucesión de Fibonacci. Calcula uno por uno todos los números hasta llegar al número n. El tiempo de ejecución es proporcional a n.

El orden en que se calculan las cosas en la solución recursiva es muy distinta. Pensemos por ejemplo que haría si le pedimos que calcule Fibonacci(5):

Al llamar a la función Fibonacci(5), esta llama a Fibonacci(4) y a Fibonacci(3) y suma sus resultados.

Fibonacci(4) llama a Fibonacci(3) nuevamente y a Fibonacci(2).

Fibonacci(3) se ejecutará entonces dos veces. Cada vez llamará a Fibonacci(2) y a Fibonacci(1).

Entonces Fibonacci(2) se ejecuta tres veces, y Fibonacci(1) se ejecuta dos.

Como se ve, algunos valores de la sucesión se calculan varias veces. No necesita ser mucho más grande n para que las repeticiones sean tantas que el algoritmo sea impracticable debido al tiempo que tarda y la memoria que consume.

Les recomiendo que implementen estos dos algoritmos y vean la diferencia. Cuando n>46 el resultado no entra en un LongInt, si se quiere calcular Fibonacci(n) para n>46 se deben usar las técnicas explicadas en la lección sobre sumas de enteros largos.

Como conclusión, los métodos recursivos suelen ser muy buenos para simplificar la programación. La pregunta que debemos hacernos es si el tiempo que vamos a ahorrar programando es mayor al que vamos a perder en la ejecución del programa. Generalmente la respuesta es afirmativa.

Como último ejemplo aquí hay uno que calcula la suma de las cifras de n:

Function SumDig(N:LongInt):LongInt;
begin
	if N=0 Then SumDig:=0
		 else SumDig:=SumDig(N div 10) + (N mod 10);
end;

Hay algunas maneras de hacer que los procesos recursivos sean bastante más eficientes. Pero eso quedará para la próxima lección.

Ejercicios:

1. Probar que el tiempo que tarda en ejecutarse la versión recursiva de Fibonacci(n) es proporcional al resultado que retorna.
   
2. Implementar recursivamente la función Fibonacci de manera que su tiempo de ejecución sea proporcional a n (Pista: hagan que la función retorne dos valores, F(n) y F(n-1)).
   
3. Dado un entero n se define la siguiente sucesión:
   a(0)=k
   a(n) = 3*n + 1 si n es impar
   a(n) = n / 2 si n es par.
   Hacer un programa que dado el número entero k, retorne el menor valor de n tal que a(n)=1.
   
4. Programar una función que dado un número entero retorne el número que se forma al escribir las cifras en orden inverso (ejemplo F(1254)=4521)
   
5. (Muy difícil) Hallar la última cifra distinta de cero de 1000.000.000!
   

Lecciones siguientes:

Recurrencia con tablas