Práctica sobre funciones

Funciones recursivas:

Una función es recursiva cuando el cuerpo de la función utiliza a la propia función. Dentro de una función recursiva suelen distinguirse dos partes:
 -   Los casos base: Son aquellos que para su solución no requieren utilizar la función que se está definiendo.
 -   Los casos recursivos: Son aquellos que sí que requieren utilizar la función que se está definiendo.
Las definiciones recursivas funcionan siempre y cuando las llamadas recursivas se realicen de forma que en algún momento se lleguen a los casos base.

Una función es recursiva final cuando tras la llamada recursiva no hay que realizar ningún cómputo adicional. Es decir, el valor devuelto en la llamada recursiva es igual al valor que debe devolver la función.
 

Ejemplos

    Para calcular el factorial de un número se distinguen dos casos: si el número es cero o si es mayor. El primer caso es un caso base, pues sabemos que la solución es 1, mientras que para el resto de los casos utilizaremos una llamada recursiva. La distinción de casos puede realizarse por cualquiera de los 4 métodos que conocemos. Veámoslo por ejemplo con el uso de patrones:

    fact 0 = 1
    fact n = n * fact (n-1)

Nótese que la recursión terminará para cualquier valor de entrada positivo, pues en cada llamada recursiva el parámetro se va decrementando, hasta que en algún momento llegue a valer 0. Nótese también que la recursión no es final, pues tras la llamada recursiva es necesario multiplicar el valor obtenido por el parámetro de entrada.

La función anterior puede convertirse en final si se añade un parámetro acumulador:

    fact n = fact' n 1
    fact' 0 acum = acum
    fact' n acum = fact' (n-1) (n*acum)

La recursión es una estrategia muy potente cuando se utilizan listas. Veamos por ejemplo cómo calcular la longitud de una lista:

    long [] = 0
    long (x:xs) = 1 + long xs

Nótese que la distinción de casos se hace en base a si la lista es vacía o no. Sabemos que la definición termina porque en cada llamada recursiva se reduce en una unidad la longitud de la lista, por lo que en algún momento llegará a estar vacía.
 

Errores típicos:

• El orden de las alternativas es muy importante en presencia de funciones recursivas, pues un orden erróneo puede provocar que la recursión no termine nunca.
• Al definir una función por patrones, es posible equivocarse al escribir el nombre de la función en alguna de las definiciones. En dicho caso, la función fallará, y si ha afectado a los casos base, posiblemente no terminará.