{"id":2949,"date":"2018-03-12T10:26:08","date_gmt":"2018-03-12T15:26:08","guid":{"rendered":"https:\/\/www.manualjava.net\/?p=2949"},"modified":"2018-03-14T15:09:51","modified_gmt":"2018-03-14T20:09:51","slug":"recursividad","status":"publish","type":"post","link":"https:\/\/www.manualjava.net\/?p=2949","title":{"rendered":"Recursividad"},"content":{"rendered":"

\"\"<\/p>\n

La recursividad es aquella propiedad que posee un m\u00e9todo por la cual puede llamarse a si mismo. Aunque se puede utilizar la recursividad como una alternativa a la iteraci\u00f3n, una soluci\u00f3n recursiva es, normalmente, menos eficiente en t\u00e9rminos de tiempo de computadora que una soluci\u00f3n iterativa, debido a las operaciones auxiliares que llevan consigo las invocaciones suplementarias a los m\u00e9todos.\u00a0<\/span><\/p>\n

Los programas examinados hasta ahora, generalmente estructurados, se componen de una serie de m\u00e9todos que se llaman de modo disciplinado. En algunos problemas es \u00fatil disponer de m\u00e9todos que se llamen a s\u00ed mismos. Un m\u00e9todo recursivo es aquel que se llama a s\u00ed mismo, bien directamente o bien indirectamente, a trav\u00e9s de otro m\u00e9todo. La recursividad es un t\u00f3pico importante examinado frecuentemente en cursos que estudian la resoluci\u00f3n de algoritmos y en cursos relativos a estructuras de datos.<\/span><\/p>\n

Sin embargo, un m\u00e9todo que tiene sentencias entre las que se encuentra al menos una que llama al propio m\u00e9todo se dice que es\u00a0recursivo.\u00a0<\/strong>As\u00ed, supongamos que se dispone de dos m\u00e9todos metodo1 y metodo2. La organizaci\u00f3n de una aplicaci\u00f3n no recursiva adoptar\u00eda una forma similar a esta:<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0metodo1(. . .){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 . . .<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0metodo2(. . .){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 . . .<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 metodo1();\u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/ llamada al metodo1<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 . . .<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

Con una organizaci\u00f3n recursiva, se tendr\u00eda esta situaci\u00f3n:<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0metodo1(. . .){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 . . .<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 metodo1();<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 . . .<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

Ejemplo<\/span><\/strong><\/h3>\n

Algoritmo recursivo de la funci\u00f3n matem\u00e1tica que suma los N primero n\u00fameros enteros positivos.<\/span><\/p>\n

Como punto de partida, se puede afirmar que para n = 1 se tiene que la suma S(1) = 1. Para n = 2 se puede escribir S(2) = S(1) + 2; en general, y aplicando la inducci\u00f3n matem\u00e1tica, se tiene:<\/span><\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0S(N) = S(N-1) + N<\/span><\/span><\/p>\n

Se est\u00e1 definiendo la funci\u00f3n suma S() respecto de s\u00ed misma, eso s\u00ed, siempre para un caso m\u00e1s peque\u00f1o. S(2) respecto a S(1), S(3) respecto a S(2) y, en general S(N) respecto a S(N-1).<\/span><\/p>\n

El algoritmo que determina la suma de modo recursivo ha de tener presente una condici\u00f3n de salida o una condici\u00f3n de parada. As\u00ed, en el caso del c\u00e1lculo de S(6); la definici\u00f3n es S(6) = 6 + S(5), a su vez S(5) es 5 + S(4), este proceso contin\u00faa hasta S(1) = 1 por definici\u00f3n. En matem\u00e1ticas la definici\u00f3n de una funci\u00f3n en t\u00e9rminos de s\u00ed misma se denomina definici\u00f3n inductiva y, de forma natural, conduce a una implementaci\u00f3n recursiva. El caso base S(1) = 1 es esencial dado que se detiene, potencialmente, una cadena de llamadas recursivas. Este caso base o condici\u00f3n de salida debe fijarse en cada soluci\u00f3n recursiva. La implementaci\u00f3n del algoritmo es:<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0int sumaEnteros(int n){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 if(n==1)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/ caso base<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return 1;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 else<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return n+sumaEnteros(n-1);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

A tener en cuenta<\/strong><\/span><\/h3>\n

La formulaci\u00f3n recursiva de una funci\u00f3n matem\u00e1tica puede ser muy ineficiente sobre todo si se repiten c\u00e1lculos realizados anteriormente. En estos casos el algoritmo iterativo, aunque no sea tan evidente, es notablemente m\u00e1s eficiente.<\/span><\/p>\n

M\u00e9todos recursivos<\/span><\/strong><\/h2>\n

Un m\u00e9todo recursivo es un m\u00e9todo que se invoca a s\u00ed mismo de forma directa o indirecta. En recursi\u00f3n directa, el c\u00f3digo del m\u00e9todo f() contiene una sentencia que invoca a f(), mientras que en recursi\u00f3n indirecta, el m\u00e9todo f() invoca a un m\u00e9todo g() que a su vez invoca al m\u00e9todo p(), y as\u00ed sucesivamente hasta que se invoca de nuevo al m\u00e9todo f().<\/span><\/p>\n

Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre s\u00ed mismo. Cualquier algoritmo que genere una secuencia de este tipo no puede terminar nunca. En consecuencia la definici\u00f3n recursiva debe incluir una condici\u00f3n de salida, que se denomina\u00a0componente base,\u00a0<\/strong>en el que f(N) se defina directamente (es decir, no recursivamente) para uno o m\u00e1s valores de N.<\/span><\/p>\n

En definitiva, debe existir una \u00abforma de salir\u00bb de la secuencia de llamadas recursivas. As\u00ed, en el algoritmo que calcula la suma de los N primeros n\u00fameros enteros:<\/span><\/p>\n

\"\"<\/p>\n

la condici\u00f3n de salida o componente base es S(N) = 1 para N = 1. Un m\u00e9todo recursivo correcto debe incluir un componente base o condici\u00f3n de salida ya que, en caso contrario se produce una recursi\u00f3n infinita.<\/span><\/p>\n

A tener en cuenta<\/strong><\/span><\/h3>\n

Un m\u00e9todo es recursivo si se llama a s\u00ed mismo, directamente o bien indirectamente a trav\u00e9s de otro m\u00e9todo. Es necesario contemplar un caso base que determina la salida de las llamadas recursivas.<\/span><\/p>\n

Ejemplo<\/strong><\/span><\/h3>\n

Hacer un m\u00e9todo recursivo que calcule el factorial de un n\u00famero y un programa que pida un n\u00famero entero y reportar su factorial.<\/span><\/p>\n

La componente base del m\u00e9todo recursivo que calcula el factorial es que n = 0 o incluso n = 1, ya que en ambos caso el factorial es 1.\u00a0El problema se resuelve recordando la definici\u00f3n expuesta anteriormente del factorial:<\/span><\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0n! = 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 si n = 0\u00a0 o\u00a0 n = 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0(componente o caso base)<\/strong><\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0n! = n(n-1)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0si n>1<\/span><\/p>\n

En la implementaci\u00f3n no se realiza tratamiento de error, que puede darse en el caso de calcular el factorial de un n\u00famero negativo.<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0import java.io.IOException;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0import java.util.Scanner;<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0public class FactorialRecursivo {<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 public static int Factorial(int n){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if(n<=1)<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return 1;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0else<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return n*Factorial(n-1);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 } <\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 public static void main(String[] args) throws IOException {<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Scanner entrada = new Scanner(System.in);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0int numero;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0do{<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0System.out.print(\u00abIngresar numero: \u00ab);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0numero = entrada.nextInt();<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0}while(numero<0);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0System.out.println(\u00ab\\t\u00bb +numero+ \u00ab!: \u00bb + Factorial(numero));<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 } <\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

Recursividad indirecta<\/strong><\/span><\/h2>\n

La recursividad indirecta se produce cuando un m\u00e9todo llama a otro, que eventualmente terminar\u00e1 llamando de nuevo al primer m\u00e9todo.<\/span><\/p>\n

Ejemplo<\/strong><\/span><\/h3>\n

Mostrar por pantalla el alfabeto, utilizando recursi\u00f3n indirecta.<\/span><\/p>\n

El m\u00e9todo main() llama a metodoA() con el argumento ‘Z’ (la \u00faltima letra del alfabeto). Este examina su par\u00e1metro c, si c est\u00e1 en orden alfab\u00e9tico despu\u00e9s que ‘A’, llama a metodoB(), que inmediatamente invoca a metodoA() pas\u00e1ndole un par\u00e1metro predecesor de c. Esta acci\u00f3n hace que metodoA() vuelva a examinar c, y nuevamente llame a metodoB(). Las llamadas contin\u00faan hasta que c sea igual a ‘A’. En este momento, la recursi\u00f3n termina ejecutando System.out.println() veintis\u00e9is veces y visualiza el alfabeto, car\u00e1cter a car\u00e1cter.<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0public class AlfabetoRecursivo {<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 public static void metodoA(char c){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if(c>’A’)<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 metodoB(c);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 System.out.println(c);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 public static void metodoB(char c){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0metodoA(\u2013\u2013c);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 public static void main(String[] args) {<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0System.out.println();<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0metodoA(‘Z’);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0System.out.println();<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 }\u00a0\u00a0<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

La recursividad es aquella propiedad que posee un m\u00e9todo por la cual puede llamarse a si mismo. Aunque se puede utilizar la recursividad como una alternativa a la iteraci\u00f3n, una soluci\u00f3n recursiva es, normalmente, menos eficiente en t\u00e9rminos de tiempo de computadora que una soluci\u00f3n iterativa, debido a las operaciones auxiliares que llevan consigo las … <\/p>\n

Seguir leyendo<\/a><\/p>\n","protected":false},"author":1,"featured_media":2958,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"_links":{"self":[{"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts\/2949"}],"collection":[{"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2949"}],"version-history":[{"count":42,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts\/2949\/revisions"}],"predecessor-version":[{"id":3002,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts\/2949\/revisions\/3002"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/media\/2958"}],"wp:attachment":[{"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2949"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2949"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2949"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}