Práctica sobre funciones

 

Concepto de funciones recursivas 

Es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.

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

1. 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.  Por ejemplo con el uso de patrones:

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

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. 

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)

2. 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.

3. Imprimir los números de 1 a 5 en pantalla utilizando recursividad.

Programa:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Recursividad4
{
    public class Recursividad
    {

        void Imprimir(int x)
        {
            if (x > 0)
            {
                Imprimir(x - 1);
                Console.WriteLine(x);
            }
        }

        static void Main(string[] args)
        {
            Recursividad re = new Recursividad();
            re.Imprimir(5);
            Console.ReadKey();
        }
    }
}