UNIDAD V
Recursividad

Introducción

La recursividad es aquella propiedad que posee una función por la cual dicha función puede llamarse a sí misma. Se puede utilizar la recursividad como una alternativa a la iteración. Una solución recursiva es normalmente menos eficiente en términos de tiempo de computadora que una solución iterativa debido a las operaciones auxiliares que llevan consigo las llamadas suplementarias a las funciones; sin embargo, en muchas circunstancias el uso de la recursión  permite a los programadores especificar soluciones naturales, sencillas, que serían, en caso contrario, difíciles de resolver. Por esta causa, la recursión es una herramienta poderosa e importante en la resolución de problemas y en la programación.

Un subprograma recursivo es un subprograma que se llama a sí mismo ya sea directa o indirectamente. Así si se dispone de dos procedimientos proc1 y proc2 , la organización podría adoptar cualquiera de las siguientes formas:

5.2 Recursión Directa

Si una función, procedimiento o método se invoca así misma, el proceso se denomina recursión directa. Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre sí mismo. Cualquier algoritmo que genere una secuencia de este tipo no puede terminar nunca o hasta que la memoria se agote. En consecuencia, la definición recursiva debe incluir un componente base (condición de salida) en el que f(n) se defina directamente (es decir, no recursivamente) para uno o más valores de n.

Ejemplo: 
Así en la función f(n) = n! (factorial)para n entero:

La condición de salida o base es f(n) = 1 para n = 0.

En el caso de la función factorial, la condición de salida puede ser cuando el número sea 1 o 0, ya que en ambos casos el factorial es 1.

5.3 Recursión Indirecta

Si una función, procedimiento o método puede invocar a una segunda función, procedimiento o método que a su vez invoca a la primera, este proceso se conoce como recursión indirecta o mutua.
Ejemplo:

El programa principal llama al procedimiento recursivo A( ) con el argumento ‘Z’. El procedimiento A examina su parámetro c. Si c está en orden alfabético después que ‘A’, el procedimiento llama a B( ), que inmediatamente llama a A( ), pasándole un parámetro predecesor de c. Esta acción hace que A( ) vuelva a examinar c, y nuevamente una llamada a B( ), hasta que c sea igual a ‘A’. En este momento la ejecución termina escribiendo veintiséis veces y visualizando el alfabeto, carácter a carácter.

5.4 Recursión vs. Iteración

Comparemos los dos enfoques y examinaremos las razones por las que el programador puede elegir un enfoque u otro según  la situación específica.

5.5 Recursión Infinita

Un bucle infinito ocurre si la prueba o test de continuación de bucle nunca se vuelve falsa; una recursión infinita ocurre si la etapa de recursión no reduce el problema en cada ocasión de modo que converja sobre el caso base o condición de salida.

En realidad la recursión infinita significa que cada llamada recursiva produce otra llamada recursiva y ésta a su vez otra llamada recursiva y así para siempre. En la práctica dicho código se ejecutará hasta que la computadora agota la memoria disponible y se produzca una terminación anormal del programa.

El flujo de control de un algoritmo recursivo requiere tres condiciones para una terminación normal:

• Un test para detener (o continuar) la recursión (condición de salida o caso base).
• Una llamada recursiva (para continuar la recursión).
• Un caso final para terminar la recursión.

Ejemplos - Aplicación

Funciones
Realizar un programa que introduzca un número entero n  y que calcule su factorial n!
Condiciones:

Algoritmo:

Codificación:   En lenguaje C.

#include<conio.h>
#include<stdio.h>

 int  x;
 float  resul;

float Fact (int n)
{
    if  ((n==1) || (n==0) )
           return 1;
    else
         return (n * fact (n-1));
}

void main()
{
      clrscr();
      printf(”Introduzca un número entero”) ;
scanf(“%d”, &x);
      resul= Fact(x);
      printf( “%d  != %f ”, x, resul);
getch();
}

Procedimientos
Realizar un programa que permita escribir el abecedario en orden ascendente.
Algoritmo:

                procedimiento A(c:caracter)
                inicio
                    Si (c>’A’) entonces
                        B(c)
                    sino
                         escribe (c)
                fin_procedimiento 

                Inicio {Programa principal}
                  A(‘Z’)
                Fin_ programa

EJERCICIO  # 6: Aplicar el Concepto de Recursividad

HERRAMIENTAS, MATERIALES Y EQUIPOS:

• Hojas blancas, lápiz
• Lenguaje C#
• Pc

PROCEDIMIENTO:

• Resuelva cada uno de los ejercicios de acuerdo al procedimiento que se indica.
• Elabore el algoritmo de cada uno de los problemas planteados.
• Codifique los algoritmos en Lenguaje C#.
• Compruebe que la ejecución y sus resultados  sean correctos.

EVIDENCIAS:
            Documentos:

• Hoja de presentación
• Algoritmos de cada uno de los ejercicios.
• Diagramas de Flujo de cada método.
• Impresión del Código en el lenguaje C#.
• Impresión de la ejecución. (Pantalla con resultados)
• Conclusión.

           Programas:

• Toda la carpeta
• Todos los ejercicios serán entregados en un solo disco. (El disco debe traer su etiqueta correspondiente).

PLANTEAMIENTO DE PROBLEMAS:

6.1 La suma de una serie de números consecutivos de 1 se puede definir recursivamente como:

Suma(1) = 1
Suma(n) = n + suma (n-1)
Escribir la función recursiva que acepte n como  un argumento  y calcule la suma de los números de 1 a n.

6.2 El valor de xn se puede definir recursivamente como:

X0 = 1
Xn = x * xn-1
Escriba un método recursivo que calcule y devuelva el valor de xn.

6.3 Reescribir el método del ejercicio 6.2 de modo que utilice un algoritmo repetitivo para calcular el valor de xn.

6.4 Números de Fibonacci

Los números de Fibonacci se definen como:
FN = FN-1 + FN-2            para N > 2
F0 = F1 = 1
que definen la secuencia:
1,1,2,3,5,8,13,21,34,55,89,144, .....

Por ejemplo, si quisiéramos encontrar Fibonacci de 5, entonces:

Fibonacci (5) = Fibonacci (4) + Fibonacci (3)
Fibonacci (4) = Fibonacci (3) + Fibonacci (2)
Fibonacci (3) = Fibonacci (2) + Fibonacci (1)
Fibonacci (2) = Fibonacci (1) + Fibonacci (0)

6.5 Desarrolle una función para calcular recursivamente el número de ocurrencias del elemento elem en el vector A.

6.6 Desarrolle una función recursiva para saber si un carácter dado se encuentra presente en una cadena de caracteres.

6.7 Dado un número entero, obtenga la tabla de multiplicar de dicho número.

6.8 Leer un número entero positivo n<10. Genere el triangulo de pascal, de acuerdo a los siguientes coeficientes binomiales:

C(n, 0) = 1
C(n, n) = 1
C(n, k) = C(n-1, k-1) + C(n-1, k)

1
1          1
1          2          1
1          3          3          1
1          4          6          4          1
…

La recursividad es una alternativa la iteración en la resolución de algunos problemas matemáticos. Los aspectos más importantes a tener en cuenta en el diseño y construcción de métodos recursivos son los siguientes:

• Un algoritmo recursivo debe tener dos partes: una parte de terminación en la que se deja de hacer llamadas, es el caso base, y una llamada recursiva con sus propios parámetros.
• Los problemas que no sea necesario una solución recursiva deberán seguirse resolviendo mediante algoritmos iterativos.
• Todo algoritmo recursivo puede ser transformado en otro de tipo iterativo, pero para ello se necesita utilizar pilas donde almacenar los cálculos parciales.
• Los métodos recursivos utilizan memoria extra en las llamadas; existe un límite en las llamadas, que depende de la memoria de la computadora, de lo contrario ocurre un error de overflow.
• Evitar que el algoritmo recursivo produzca llamadas infinitas.

Para asegurarse que el algoritmo recursivo es correcto debe cumplir los sig. Requisitos

• No existe recursión infinita.
• Cuenta con una condición de terminación, que devuelve el valor correcto.
• Que cada llamada recursiva devuelva el valor correcto, por lo tanto, el final también será correcto.