{"id":3031,"date":"2018-03-14T22:22:09","date_gmt":"2018-03-15T03:22:09","guid":{"rendered":"https:\/\/www.manualjava.net\/?p=3031"},"modified":"2018-03-16T17:02:32","modified_gmt":"2018-03-16T22:02:32","slug":"recursion-o-iteracion","status":"publish","type":"post","link":"https:\/\/www.manualjava.net\/?p=3031","title":{"rendered":"Recursi\u00f3n o iteraci\u00f3n"},"content":{"rendered":"

\"\"<\/p>\n

Se han estudiado diferentes m\u00e9todos que se pueden implementar f\u00e1cilmente, bien de modo recursivo, o bien de modo iterativo. En esta secci\u00f3n se comparan los dos enfoques y se examinan las razones por las que el programador puede elegir un enfoque u otro seg\u00fan la situaci\u00f3n espec\u00edfica.\u00a0<\/span><\/p>\n

Tanto la iteraci\u00f3n como la recursi\u00f3n se basan en una estructura de control: la iteraci\u00f3n utiliza una estructura repetitiva mientras que la recursi\u00f3n utiliza una estructura de selecci\u00f3n. Tanto la iteraci\u00f3n como la recursi\u00f3n implican repetici\u00f3n: la iteraci\u00f3n utiliza expl\u00edcitamente una estructura repetitiva mientras que la recursi\u00f3n consigue la repetici\u00f3n mediante llamadas repetidas al m\u00e9todo.<\/span><\/p>\n

La iteraci\u00f3n y la recursi\u00f3n implican cada una un test de terminaci\u00f3n (condici\u00f3n de parada). La iteraci\u00f3n termina cuando la condici\u00f3n del bucle no se cumple, mientras que la recursi\u00f3n termina cuando se reconoce un caso base o alcanza la condici\u00f3n de parada. La recursi\u00f3n tiene muchas desventajas. Se invoca repetidamente al mecanismo de llamadas a m\u00e9todos y, en consecuencia, se necesita un tiempo suplementario para realizar cada llamada.<\/span><\/p>\n

Esta caracter\u00edstica puede resultar cara en tiempo de procesador y espacio de memoria. Cada llamada recursiva produce una nueva creaci\u00f3n y copia de las variables de la funci\u00f3n, esto consume m\u00e1s memoria e incrementa el tiempo de ejecuci\u00f3n. Por el contrario, la iteraci\u00f3n se produce dentro de un m\u00e9todo, de modo que las operaciones suplementarias en la llamada al m\u00e9todo y en la asignaci\u00f3n de memoria adicional son omitidas.<\/span><\/p>\n

Entonces, \u00bfCu\u00e1les son las razones para elegir la recursi\u00f3n?. La raz\u00f3n fundamental es que existen numerosos problemas complejos que poseen naturaleza recursiva y, en consecuencia, son m\u00e1s f\u00e1ciles de implementar con algoritmos de este tipo. Sin embargo, en condiciones cr\u00edticas de tiempo y de memoria; es decir, cuando el consumo de tiempo y memoria sean decisivos o concluyentes para la resoluci\u00f3n del problema, la soluci\u00f3n a elegir debe ser, normalmente, la iterativa.<\/span><\/p>\n

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

Cualquier problema que se pueda resolver recursivamente tiene, al menos, una soluci\u00f3n iterativa utilizando una pila. Un enfoque recursivo se elige, normalmente, con preferencia a un enfoque iterativo cuando resulta m\u00e1s natural para la resoluci\u00f3n del problema y produce un programa m\u00e1s f\u00e1cil de comprender y de depurar. Otra raz\u00f3n para elegir una soluci\u00f3n recursiva es que una soluci\u00f3n iterativa puede no ser clara ni evidente.<\/span><\/p>\n

Consejo de programaci\u00f3n<\/strong><\/span><\/h3>\n

Se ha de evitar utilizar recursividad en situaciones de rendimiento cr\u00edtico o exigencia de altas prestaciones en tiempo y en memoria, ya que las llamadas recursivas emplean tiempo y consumen memoria adicional. No es conveniente el uso de una llamada recursiva para sustituir un simple bucle.<\/span><\/p>\n

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

Dado un n\u00famero natural n, obtener la suma de los d\u00edgitos de que consta. Presentar un algoritmo recursivo y otro recursivo.<\/span><\/p>\n

El ejemplo ofrece una muestra clara de comparaci\u00f3n entre la resoluci\u00f3n de modo iterativo y de modo recursivo. Se asume que el n\u00famero es natural y que, por tanto, no tiene signo. La suma de los d\u00edgitos se puede expresar:<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0suma = modulo(n,10) + suma(n\/10)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 para n>10<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0suma = n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 para n<10, caso base<\/span><\/p>\n

Para, por ejemplo: n = 259<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0suma = modulo(259,10) + suma(259\/10)\u00a0 \u00a0 \u00a0 \u2192<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 2 + 5 + 9 = 16<\/span>
\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0\u2193<\/strong><\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0suma = modulo(25,10) + suma(25\/10)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u2192<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 2 + 5\u00a0 \u00a0\u2191<\/strong><\/span>
\n \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0\u2193<\/strong><\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0suma = modulo(2,10) + suma(2\/10)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u2192<\/strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 2\u00a0 \u00a0 \u2191<\/strong><\/span><\/p>\n

El caso base, el que se resuelve directamente, es n<10 y, a su vez, es la condici\u00f3n de parada.<\/span><\/p>\n

Soluci\u00f3n recursiva<\/strong><\/span><\/h3>\n

\u00a0 \u00a0 \u00a0 \u00a0public static int sumaRecursiva(int n){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if(n<10)<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 return n;<\/span>
\n\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 return (n%10)+sumaRecursiva(n\/10);<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

Soluci\u00f3n iterativa<\/strong><\/span><\/h3>\n

La soluci\u00f3n iterativa se construye con un bucle mientras, repitiendo la acumulaci\u00f3n del resto de dividir n por 10 y actualizando n en el cociente. La condici\u00f3n de salida del bucle es que n sea igual a 0.<\/span><\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0public static int sumaIterativa(int n){<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0int suma = 0, digito;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0while(n!=0)<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0{ <\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0digito = n % 10;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0suma = suma + digito;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0n = n \/10;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0}<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return suma;<\/span>
\n\u00a0 \u00a0 \u00a0 \u00a0}<\/span><\/p>\n

Directrices en la toma de decisi\u00f3n iteraci\u00f3n\/recursi\u00f3n<\/span><\/strong><\/h3>\n
    \n
  1. Consid\u00e9rese una soluci\u00f3n recursiva s\u00f3lo cuando una soluci\u00f3n iterativa sencilla no sea posible.<\/span><\/li>\n
  2. Util\u00edcese una soluci\u00f3n recursiva s\u00f3lo cuando la ejecuci\u00f3n y eficiencia de la memoria de la soluci\u00f3n est\u00e9 dentro de l\u00edmites aceptables, considerando las limitaciones del sistema.<\/span><\/li>\n
  3. Si son posibles las dos soluciones, iterativa y recursiva, la soluci\u00f3n recursiva siempre requerir\u00e1 m\u00e1s tiempo y espacio debido a las llamadas adicionales a los m\u00e9todos.<\/span><\/li>\n
  4. En ciertos problemas, la recursi\u00f3n conduce a soluciones que son mucho m\u00e1s f\u00e1ciles de leer y de comprender que su alternativa iterativa. En estos casos, los beneficios obtenidos con la claridad de la soluci\u00f3n suelen compensar el coste extra (en tiempo y memoria) de la ejecuci\u00f3n de un programa recursivo.<\/span><\/li>\n<\/ol>\n

    Consejo de programaci\u00f3n<\/strong><\/span><\/h3>\n

    Un m\u00e9todo recursivo que tiene la llamada recursiva como \u00faltima sentencia (recursi\u00f3n final) puede transformarse f\u00e1cilmente en iterativa reemplazando la llamada mediante un bucle condicional que chequee el caso base.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

    Se han estudiado diferentes m\u00e9todos que se pueden implementar f\u00e1cilmente, bien de modo recursivo, o bien de modo iterativo. En esta secci\u00f3n se comparan los dos enfoques y se examinan las razones por las que el programador puede elegir un enfoque u otro seg\u00fan la situaci\u00f3n espec\u00edfica.\u00a0<\/p>

    Seguir leyendo<\/a><\/p>\n","protected":false},"author":1,"featured_media":3048,"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\/3031"}],"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=3031"}],"version-history":[{"count":22,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts\/3031\/revisions"}],"predecessor-version":[{"id":3070,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/posts\/3031\/revisions\/3070"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=\/wp\/v2\/media\/3048"}],"wp:attachment":[{"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3031"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3031"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.manualjava.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}