Recurción

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 nes 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) calculacorrectamente 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  tieneotra 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 Fnal 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 primermes, 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 elproblema 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 tucompilador 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...