UNIDAD 2 RECURSIVIDAD 

Contenidos	Página
2.1 Definición	1
2.2 Procedimientos recursivos	2
2.3 Ejemplos de casos recursivos	2

2. RECURSIVIDAD                                                                              * * * EJEMPLOS AL FINAL * * *

2.1 Definición

Recursión es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición, las instancias complejas de un proceso se definen en términos de instancias más simples, estando las finales más simples definidas de forma explícita.

(Nota: aunque los términos "recursión" y "recursividad" son ampliamente empleados en el campo de la informática, el término correcto en castellano es recurrencia)
La recursión permite definir un objeto en términos de sí mismo. Casos típicos de estas estructuras de datos definidas de manera recursiva son los árboles y las listas ligadas.

Existe la recursión de dos maneras:

1. Directa: el subprograma se llama directamente a sí mismo.

Subprograma P                    

 

2. Indirecta: Se da cuando un subprograma llama a otro programa y éste a su vez llama al primero.

P

                                                                                                           
En toda definición recursiva de un problema se debe establecer un estado básico. Es decir un estado en el cual la solución no se presente de manera recursiva sino directamente. Además la entrada (datos) del problema debe ir acercándose al estado básico.

Si dado un problema es posible determinar el estado básico entonces se puede llegar a una solución, de otra forma estaríamos frente a una definición circular del problema.

2.2 Procedimientos recursivos

Los procedimientos recursivos son la forma más natural de representación de muchos algoritmos. Como ejemplo, elaboremos una función que nos permita calcular el factorial de un número:
Matemáticamente se define como factorial de un número n al producto de los enteros positivos desde 1 hasta n y se denota por n!

n! = 1 . 2 . 3 . 4 . 5 . . . (n – 2) (n – 1) n

También se define 0! = 1, de forma que la función está definida para todos los enteros no negativos. Así tenemos que:

0! = 1 1! = 1 2! = 1 . 2 = 2 3! = 1 . 2 . 3 = 6

4! = 1 . 2 . 3 . 4 = 24 5! = 1 . 2 . 4 . 5 = 120

y así sucesivamente.

Algoritmo Factorial FACTORIALREC(N)

[ Este algoritmo calcula el factorial de un número N, donde N es un valor numérico entero positivo o nulo]

Si N=0

      Entonces
                  Hacer FACTORIALREC = 1 [Estado Básico]
      Si no
                  Hacer FACTORIALREC=N*FACTORIALREC(N-1) [Llamada Recursiva]

[Fin del condicional del paso 1]

En el cálculo de la  Serie de Fibonacci de un número también se puede aplicar la Recursión.

2.3 Ejemplos de casos recursivos

Programa Recursivo:

Class factorial recdato{ static int factorialrec(int n) { int rec;if(n==0) rec=1; else rec=n*factorialrec(n-1); return rec;} public static void main (String[] args) { int dato; int f; System.out.print(" \t\t\tDAME DATO: "); dato=TextIO.getlnInt(); f=factorialrec(dato) System.out.println("\t\t\t\t"+"DATO "+dato+"factorial"+ f); } }

Otro ejemplo clásico de problemas definidos recursivamente es el cálculo de la serie de Fibonacci: 0,1,1,2,3,5,8,13,21,...etc. Recuérdese que el Fibonacci de un número se obtiene de la suma de los dos números Fibonacci anteriores.

Programa:

class fibonacci { static int fibonaccirec(int n) { int rec; if (n<=1) rec=1; else rec=fibonaccirec(n-1)+fibonaccirec(n-2); return rec;}//fin class public static void main (String[] args) { int dato; int f; System.out.print(" \t\t\tDAME NUMERO DE VECES PARA CALCULAR FIBONACCI : "); dato=TextIO.getlnInt(); f=fibonaccirec(dato); System.out.println("\t\t\t\t"+"DATO "+dato+" fibonacci es "+ f); } }

Link de descarga de programa recursivo en netbeans