2.6 Funciones recursivas

 Dentro de una función se puede ejecutar cualquier tipo de instrucción e incluso llamar a cualquier otra función. También es posible, con ciertas restricciones, que una función se llame a sí misma. Una función que se invoca a sí misma es una función recursiva.

Veamos una vez más el ejemplo de la función factorial que vimos en la sección anterior.

 

El programa principal es el mismo, pero la función es distinta. Sólo tiene un if que pregunta si n es igual a 1. Si es así, devuelve 1 (el factorial de 1 es 1). Si n es mayor que 1, podemos calcular su factorial como n multiplicado por el factorial de n-1. Eso es lo que hacen las instrucciones en la rama else del if.
Cuando llamamos a la función con, por ejemplo, n = 5, la función se llama a sí misma pasando por parámetro n-1, o sea, 4. La instancia de la función en la que n era igual a 5, se queda esperando el resultado de esta nueva ejecución. Ésta a su vez se llama a sí misma otra vez con n = 3, y se queda esperando el resultado. La función se llama una cuarta vez con n = 2, y una quinta vez con n=1.
En este momento, tenemos al programa esperando el resultado de la función, y tenemos cuatro ejecuciones de la función detenidas, esperando el resultado de la instancia siguiente.  Cuando se ejecuta la quinta instancia con n = 1, la pregunta del if da verdadero y la función devuelve el valor de 1 a la función que la llamó. Allí, donde n = 2, multiplica el resultado que devolvió la función (1) por el valor de n (2) y devuelve este valor a quien la llamó. Así se va retrocediendo en la cadena de funciones abiertas, hasta devolver el factorial de 5 al programa principal.

Es importante tener una condición que evite que la función continúe llamándose a sí misma hasta el infinito. La función puede llamarse a sí misma, pero no siempre: Tiene que haber alguna instancia que termine la función sin llamarse a sí misma. Esta condición es llamada condición de corte. En este ejemplo, la condición de corte es n=1: Cuando n es igual a 1, la función no se llama una vez más.

Al igual que en el caso del factorial, cualquier función que se pueda escribir en forma recursiva, puede escribirse también en forma no recursiva, con un ciclo. No hay una regla clara que diga cuándo una función debe ser recursiva y cuándo no. Si bien una función recursiva ocupa más memoria y es más lenta que una iteración, en muchos casos puede ser más simple de programar e interpretar.


Como dijimos al principio, el programa principal que llama a la función es el mismo que el del capítulo anterior: Al llamar a una función, el programa no sabe si la función es recursiva o no: sólo sabe que le devuelve un entero, y que ese entero es el factorial del parámetro enviado. La forma de resolverlo, es interna de la función y está oculta al programa que la invoca.