Recursividad

La recursividad es una herramienta a disposición de algunos lenguajes de programación, aunque de apariencia simple provee un gran potencial en aplicaciones matemáticas y en programación computacional. Su empleo requiere un adecuado control de los recursos disponibles, ya que de lo contrario podría caerse en la creación de procedimientos lentos y con grandes requerimientos de memoria.

 

Un proceso recurrente no es más que un procedimiento que dentro de sus instrucciones contiene una, que llama al mismo procedimiento ejecutándose (llamada recursiva) de manera indefinida o en un ciclo que podría ser infinito.

Sobre la recursividad, es importante tener presente los siguientes aspectos:

1.       La recursividad es un recurso utilizado en programación de computadoras para definir ciclos a los que se le puede agregar condiciones para terminar su ejecución en algún momento específico.

2.       El efecto de ciclo se logra si la llamada recursiva aparece como última orden o al principio de la definición, excepto que alguna condición haga terminar el proceso.

3.       Si la llamada recursiva se encuentra en el medio o se incluyen varias de ellas, la idea de ejecución en ciclo se desvanece.

4.       Sobre el manejo de variables en las llamadas recursivas es conveniente que estas sean variables locales, definidas como parámetros del procedimiento, de manera que en cada caso existan mientras esté en ejecución la llamada recursiva.

 

Ejemplo:

El factorial de un número entero positivo se define como el producto de todos los números naturales anteriores o iguales a él.

 

Se escribe n!, y se lee "n factorial". (Por definición, el factorial de 0 es 1: 0!=1)

1! = 1 * 1 = 1

3! = 1 * 2 * 3 = 6

10! = 1 * 2 * 3 … 8 * 9 * 10 = 3 628 800

 

Escriba un algoritmo recursivo para calcular el factorial de un número entero positivo.

Solución:

Algoritmo

 

entero factorial(entero n)

                si(n < 2) return 1

                else return n * factorial(n - 1)

 

Inicio

    entero n

    escriba("Número entero positivo para calcular su factorial : ")

    leer(n)

    si(n >= 0)

                escriba(n, "! = ", factorial(n))

    sino

                escriba("El número debe ser mayor o igual a 0")

fin

 

 

Código C++

Ejemplo:

La sucesión de Fibonacci es la sucesión de números:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

Cada número se calcula sumando los dos anteriores a él: el 2 se obtiene sumando los dos números anteriores (1+1), el 3 se obtiene sumando los dos números anteriores (1+2), el 5 es (2+3), y así sucesivamente. Escriba un algoritmo que emplee recursividad, que genere n términos de la sucesión de Fibonacci a partir de 0 y 1, donde n es un valor leído.

Solución:

Algoritmo

// Generar n términos de la sucesión de Fibonacci

 

entero fib(entero a, entero b)

    retorna a + b

 

Inicio

    entero n

    entero a = 0, b = 1

 

    Escriba("Digite el número de elementos de la secuencia: ")

    Leer(n)

    Escriba(a," ",b, " ")

    para(entero i = 2; i < n; i++)

        entero temp = fib(a, b)

        Escriba(temp, " ")

        a = b

        b = temp

    fin-para

fin

 

 

Código C++

Ejemplo:

Escriba un algoritmo recursivo que convierta un valor leído n base 10 a su correspondiente expresión binaria.

Solución:

Algoritmo

// Decimal a binario

 

binario(entero n)

  if (n != 0)

    entonces

        binario(n / 2)

        escriba(n % 2)

fin-binario

Inicio

    entero num = 0;

    escriba("Convertir decimal a binario")

    escriba("Introduce un numero: ")

    leer(num)

    escriba(num, " base 10 = ")

    binario(num);

    escriba(" base 2")

fin

 

 

Código C++