2 Algunos ejemplos simples

En este capítulo describiremos algunos de los ejemplos más simples que podamos imaginar de algoritmos recursivos.

2.1 La función factorial

Alguna vez te habrás preguntado para qué sirve la tecla n! de tu calculadora. Esta tecla calcula lo que se llama el factorial de n. Esta función se define de la forma siguiente: Si n es igual a 0, entonces n! es igual a 1. Si n es mayor que 0, entonces n! es igual al producto de (n-1)! y n. Como puedes ver, definimos n! en términos de (n-1)!, que a su vez está definido en términos de ((n-1)-1)!, que a su vez... ¿Cuándo salimos del círculo vicioso? ¡Exacto! Después de n pasos, n! está definido en términos de 0!, pero como sabemos que 0! es igual a 1, no hay necesidad de continuar. Hagamos un ejemplo:

4! = 4*3! = 4*(3*2!) = 4*(3*(2*1!)) = 4*(3*(2*(1*0!))) = 4*(3*(2*(1*1))) = 4*(3*(2*1)) = 4*(3*2) =  4*6 =  24.

Por cierto, el factorial de n cuenta el número de permutaciones de n objetos distintos colocados a lo largo de una línea recta.

A continuación mostramos dos funciones recursivas, una en C y la otra en Pascal, para calcular el factorial de un entero.

C
Pascal
int factorial(int n)
{
  if (n == 0) return 1;
  else return n*factorial(n-1);
}
function factorial(n : integer) : integer
begin
  if n = 0 then factorial := 1
  else factorial := n*factorial(n-1)
end

Nota que ninguna de estas dos funciones calcula el factorial de un número entero muy grande. Usando tu compilador de C o Pascal, determina cual es el valor más grande de n para el cual factorial(n) calcula correctamente el valor de n! ¿Cómo podrías aumentar este valor?

2.2 Los conejos de Fibonacci

Cierto matemático italiano de nombre Leonardo de Pisa, pero mejor conocido como Fibonacci, propuso el siguiente problema: Suponga que acabamos de comprar una pareja de conejos adultos. Al cabo de un mes, esa pareja tiene una pareja de conejitos (un conejo y una coneja). Un mes después, nuestra primera pareja  tiene otra pareja de conejitos (nuevamente, un conejo y una coneja) y, al mismo tiempo, sus primeros hijos se han vuelto adultos. Así que cada mes que pasa, cada pareja de conejos adultos tiene una pareja de conejitos, y cada pareja de conejos nacida el mes anterior se vuelve adulta. La pregunta es, ¿cuántas parejas de conejos adultos habrá al cabo de n meses? Para resolver este problema, llamemos Fn al número de parejas adultas al cabo de n meses. No es difícil convencerse de que si n es al menos 2, entonces Fn es igual a Fn-1 + Fn-2. ¿Porqué? Así que Fn queda en términos de Fn-1 y Fn-2, que a su vez quedan en términos de Fn-2, Fn-3 y Fn-4, que a su vez... Ahora salimos del círculo vicioso recordando que al principio había una pareja de conejos adultos, la misma que había al final del primer mes, así que F0 = F1 = 1. Hagamos un ejemplo:

F4 = F3 + F2 = (F2 + F1) + (F1 + F0) = ((F1 + F0) + 1) + (1 + 1) = ((1 + 1) + 1 ) + 2 = (2 + 1) + 2 = 3 + 2 = 5.

Por si te lo preguntabas, la sucesión de números F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, etc. recibe el nombre de sucesión de Fibonacci.

A continuación mostramos dos funciones recursivas, una en C y otra en Pascal, que resuelven el problema de Fibonacci.

C
Pascal
int fib(int n)
{
  if ((n == 0) || (n == 1)) return 1;
  else return fib(n-1) + fib(n-2);
}
function fib(n : integer) : integer
begin
  if (n = 0) or (n = 1) then fib := 1
  else fib := fib(n-1) + fib(n-2)
end

Nota de nuevo que ninguna de estas dos funciones calcula el número de parejas de conejos para un número de meses muy grande. Usando tu compilador de C o Pascal, determina cual es el valor más grande de n para el cual fib(n) calcula correctamente el valor de Fn. ¿Cómo podrías aumentar este valor?

2.3 El triángulo de Pascal

En algún momento de tu vida habrás aprendido que (x + z)2 = x2 + 2xz + z2, que (x + z)3 = x3 + 3x2z + 3xz2 + z3 y, en general, para cualquier entero positivo n, a calcular los coeficientes de (x + z)n, y posiblemente le diste el nombre de nCm al coeficiente de xmzn-m. Seguramente recuerdas la siguiente tabla triangular:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . . . . .

Esa tabla se conoce como triángulo de Pascal y se construye como sigue: Al principio se coloca un 1 (que corresponde con 0C0). Para cada renglón subsecuente, digamos para el renglón n, se coloca un 1 a la izquierda y un 1 a la derecha (que corresponden con nC0 y nCn, respectivamente) y los elementos restantes se calculan sumando los dos números que tiene justo arriba a la izquierda y arriba a la derecha, es decir, nCm = n-1Cm-1 + n-1Cm para toda 0 < m < n.

Entre otras cosas, el número nCm cuenta la cantidad de formas de escoger m objetos de un total de n objetos distintos. A estos números también se les llama las combinaciones de m objetos en n.

A continuación mostramos dos funciones recursivas, una en C y otra en Pascal, que calculan el número de combinaciones de m objetos en n.

C
Pascal
int comb(int n, int m)
{
  if ((n == 0) || (n == m)) return 1;
  else return comb(n-1,m-1) + comb(n-1,m);
}
function comb(n, m : integer) : integer
begin
  if (n = 0) or (n = m) then comb := 1
  else comb := comb(n-1,m-1) + comb(n-1,m)
end

Como de costumbre, las funciones que escribimos no calculan nCm correctamente para valores grandes de n y m. ¿Qué pasa si llamamos a comb(n,m) con un valor negativo de m? ¿Y si la llamamos con un valor de m mayor a n? ¿Qué harías para evitar ese problema?

Capítulo anterior y siguiente.