Para entender la recursividad primero hay que entender la recursividad

Si ya entendiste la recursividad no leas esto.

La recursividad funciona de la siguiente manera:

  • Primero se tiene una o más condiciones base. Estas condiciones son usadas para saber cuando hay que parar.

  • Se tienen varios parámetros de entrada con los que se va a trabajar. Uno o varios de estos parámetros serán usados en las condiciones base.

  • Finalmente se tienen varias operaciones a realizar. La funcion que estamos definiendo será resuelta al llamarse a sí misma con parámetros nuevos, de lo contrario entrará en un ciclo infinito

Entonces, con esta información en mente, podemos hacer el siguiente pseudo código para ver si existe un elemento usando busqueda binaria

boolean contiene( elemento ,  lista)  {
   //¿Cual es nuestra condición base?
   //R. Saber si la lista tiene elementos ,¿no?

   if list.estaVacia()?  regresa  falso; //  el elemento no esta en la lista vacía

   // ¿Que otras condiciones base podemos intentar?
   // R. Ver si la lista tiene un solo elemento y
   // si ese elemento es el que buscamos
   if lista.tamaño() == 1
        return lista.primerElemento() == elemento
        // verdadero si son iguales y falso si no lo son.

   // Finalmente podemos intentar como condición base, si
   // nuestro elemento esta en medio
   if lista.elementoDeEnMedio() == elemento ?  return true // Encontrado

   // Bueno, ninguna de nuestras condiciones base funcionó
   // Ahora vamos a ejecutar alguna operación.
   // Aquí está la magia de la recursión:
   // resolvemos nuestro problema llamado a esta misma función ( re-cursandola )
   // con diferentes argumentos.
   // Por ejemplo aquí dividimos la lista en dos y llamamos la función
   // con la primera mitad y con la segunda

    return  contiene( elemento , lista.primeraMitad() )  
            o contiene( elemento , lista.segundaMitad() )

    // Que puede leeerse como:  
    // "La lista contiene al elemento si
    // la primera mitad contiene al elemento
    // o la segunda mitad contiene al elemento
}

Como se puede ver, cada vez que se parte la lista en dos, la lista se hace más chica, llegará al punto en que tenga un solo elemento o esté vacía. Cuando eso suceda, nuestras condiciones base pararán la recursión.

Ees mucho más fácil, si primero se identifican las condiciones base y luego se identifica como modificar los argumentos.

Es muy importante, primero intentar esto en pseudo-código o en lápiz y papel antes de intentar programarlo. Así lidiamos primero con la lógica y luego con el lenguaje de programación. Yo encuentro muy eficaz crear funciones auxiliares, que me ayuden a no atorarme cuando estoy pensando el el pseudo-codigo, es este caso las funciones auxiliares son: "primerElemento(), elementoDeEnMedio(), primeraMitad() y segundaMitad() ). Estas auxiliares no son relevante al problema, Cuando hay que implementarlo ya habrá dudas especificas, pero por lo pronto nos permiten que el pensamiento fluya.

Espero que esto ayude a entender mejor la recursividad.

Si aún no le has entendido, ve este link

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de AlexSnake

Sorprendente...

Me parece un excelente ejemplo, pero que utilidad se le puede dar en un problema real? o en que podria ocuparlo? un reporte? una busqueda?

Un reporte, una búsqueda, o

Exacto, un reporte, una búsqueda, o por ejemplo para ordenar elementos.

De hecho Java utiliza recursividad para su método de ordenamiento en Arrays.sort() que es utilizado por millones diariamente.

La recursividad es algo

La recursividad es algo tremendo y mucho más rápida que utilizar ciclos. Francamente lo puedes usar en labores tan ridículas (cómo la típica tareaita de imprimir un arreglo) así cómo ya en cosas mucho más pro (ordenamientos).

Es algo maravilloso, hay un dicho:
"To iterate is human, to recurse is divine"

Imagen de ezamudio

velocidad

Recursión es más rápida que iteración? Cuidado con esos absolutos... yo creo que depende de la implementación de tu ciclo, y del lenguaje/plataforma/arquitectura de hardware, porque aunque el principio de recursión es el mismo en cualquier plataforma, no se implementa igual en todos los lenguajes y plataformas, y por lo tanto no va a tener el mismo performance una invocación recursiva en Java que en Ruby que en PHP que en C que en C++ que en Groovy que en .NET.

Además, el uso de recursos es muy distinto. No es lo mismo recorrer los elementos de un arreglo en un ciclo iterativo, que hacerlo de manera recursiva, en donde te puedes acabar la memoria si el arreglo es muy grande porque cada llamada recursiva incrementa el uso del stack.

En términos generales la

En términos generales la recursividad es más lenta que los loops; es por eso que en algunos lenguajes se puede optimizar la recursión de cola ( tail recursion que es aquella donde la llamada ocurre al final de la función) precisamente con un loop.

De una forma similar, algunos loops pueden ser optimizados con un GOTO e incluso eliminados.

Lo interesante es precisamente que un algoritmo recursivo es más sencillo de explicar ( por que se explica a así mismo ) que su contraparte iterativa y si eventualmente se vuelve un cuello de botella, siempre puede cambiarse, solo que hay que mantener el estado de ejecución a mano.

Imagen de rugi

Otro ejemplo

Otro ejemplo, puede ser,.... busqueda sencilla:

http://www.bytemycode.com/snippets/snippet/793/

public class SearchFile {

    public static final String search(String ad, String dir) {
        String res = null;
        File[] fs = new File(dir).listFiles();
        if (fs != null) {
            //System.out.println("" + fs.length);
            for (int i = 0; i < fs.length; i++) {
                if (fs[i].isFile()) {
                    if (ad.equals(fs[i].getName())) {
                        //System.out.println("Lo encontre " + fs[i].getAbsolutePath());
                        res = fs[i].getAbsolutePath();
                        break;
                    }
                }else{
                     res = SearchFile.search(ad, fs[i].getAbsolutePath());
                }//if
            }//for
        }
        return res;
    }//method

    public static void main(String[] args) {
            if (args.length < 2){
                System.out.println("   Usar:");
                System.out.println("          java SearchFile ad [directorio] ");
                System.out.println("                ad:         Nombre del archivo o directorio a buscar.");
                System.out.println("                directorio: Directorio de busqueda. Por default el directorio actual.");
                return;
            }
            System.out.println("Archivo Encontrado en: " + SearchFile.search(args[0], args[1]));
    }
}

Re: velocidad

Igual también en loops con arreglos grandes también hay casos en donde adios RAM (recuerdos de estructuras de datos...en donde podía recorrer arreglos de 10millones de elementos con recursividad, pero no con ciclos). También siempre que probabamos búsquedas en listas era más rápida la recursividad que los ciclos. Por eso se me quedó la idea =)...de no ser así una disculpa.

Imagen de ezamudio

ejemplos

En general, cualquier algoritmo que se pueda implementar con recursión se puede implementar también de manera iterativa. La decisión entre uno y otro se puede basar en criterios como desempeño y lo entendible que quede el código. Y repito, según la plataforma puede ser más rápido usar ciclos o recursión, pero con recursión siempre vas a tener la limitante del stack.

Dos ejemplos de mundo real: vean la segunda y quinta imágenes.

Re: ejemplo

Si tienes razón he probado con Ruby y Python. En python es más rápida la recursividad en arreglos pequeños, pero en arreglos grandes de más de 3millones truena...En Ruby es más rápido el bien ponderado:

arreglo.each do |a|
#Codigo aquí
end

Si a esto el agregamos que en Ruby al elemento 8700 (más o menos) se quejaba del stack cómo tu dices. =)

**OFF TOPIC-ON RESPONSE:Jajaja...Mac-ero y anti-ms.[sarcasm] ¿Porqué el odio contra MS?, es algo que aun no entiendo. [/sarcasm]

Hice esa pregunta

Hice esa pregunta precisamente aquí http://programmers.stackexchange.com/questions/24997/can-all-the-recursi...

En resumen:
Todas las soluciones recursivas pueden ser escritas en forma no recursiva. Lo que se necesita es mantener es estado en una pila local donde se saque y ponga el elemento en turno.

Obvio, la implementación puede ser un horror. Lo que se gana con recursividad es simplicidad

Imagen de ezamudio

arreglo.each

Pero arreglo.each do |a| blabla end en Ruby es iterativo, no recursivo. Se ejecuta el código "blabla" con cada elemento de la lista; finalmente es la estructura básica de ciclos, que se puede hacer con un for por ejemplo en cualquier otro lenguaje, donde tomas un elemento de una lista y ejecutas cierto código con ese elemento.

Imagen de Nopalin

Pues yo nunca he encontrado

Pues yo nunca he encontrado como recorrer todos los elemento de una lista tipo arbol utilizando ciclos, solo recursividad, si alguien tiene algun ejemplo de como hacerlo con un for o un while, bienvenido.

Ahhh no me retes, que tengo

Ahhh no me retes, que tengo muchas flojera... :) Si si alguién lo hace que lo postee.. A ver preguntemosle a google

A méndigo Google, sabe todo:

A méndigo Google, sabe todo: Este es el primer hit ( no sé si esté correcto, además es en Sicharp ) http://vadmyst.blogspot.com/2007/09/non-recursive-binary-tree-traversal....

Re: arreglo.each.

Por eso, dije que era más rápido que la recursividad a eso me refería.

Re: A méndigo Google, sabe todo:

mmm...al parecer funciona pero sólo para árboles no balanceados (o eso es lo que me da a entender el código).

EDIT: Haciendo una revisada parece que me tendré que tragar mis palabras, si funciona para árboles balanceados también (no había visto el último else).

Imagen de ezamudio

recursión vs iteración

Nopalin, no digo que sea malo hacer algoritmos que utilicen recursión o que solamente se deba utilizar iteración o que uno sea mejor que otro. Simplemente dije que cualquier algoritmo que se implemente usando recursión, también se puede hacer con iteración. No significa que siempre uno sea mejor que otro. Ciertos problemas se resuelven mejor con recursión pero otros se resuelven mejor o son más robustos usando iteración. Lo de los árboles es un buen ejemplo porque la estructura misma se presta para recorrerla utilizando recursión; ya vimos que sí se puede hacer lo mismo con iteración, pero es más complicado. Cada uno tendrá sus ventajas y desventajas (menos código pero la limitante del stack trace vs. código más complicado y tal vez hasta menor desempeño pero puede recorrer árboles más grandes).

Buen post @OscarRyz

Obvio, la implementación puede ser un horror. Lo que se gana con recursividad es simplicidad

Yo de plano he tenido un poco de problemas al entenderle a la recursividad.

Por lo poco que he entendido hay dos tipos (o formas) de crear funciones o procedimientos recursivos:

  • Iterativos
  • Selectivos

yo del factorial y del código de Hanoi no paso ja ja ja.

En general, cualquier algoritmo que se pueda implementar con recursión se puede implementar también de manera iterativa. La decisión entre uno y otro se puede basar en criterios como desempeño y lo entendible que quede el código. Y repito, según la plataforma puede ser más rápido usar ciclos o recursión, pero con recursión siempre vas a tener la limitante del stack.

@ezamudio, me recuerdas a un profe de programación en paralelo que decia exactamente (bueno casi) lo mismo.

Imagen de benek

Groovy

Pues en la sesión de hoy del curso de Groovy, a MrDajarck se le ocurrió el ejercicio de leer un archivo con una lista de números y sacar su factorial.

Usando recursividad me quedó así:

def f = { n -> (n==0)?1:(n * call(n-1)) }
new File('/Users/benek/ejerciciogrubi.txt').eachLine { linea -> println f(Integer.valueOf(linea)) }

Con números del 1 al 10 la salida fue:

1
2
6
24
120
720
5040
40320
362880
3628800

Imagen de ezamudio

más ejemplos

Para mí, la mejor manera de calcular un factorial es iterativa. Ejemplos en Groovy y Scala para sacar 10!:

(1..10).inject(1){a,b->a*b}

Eso es básicamente un "fold left" en programación funcional. En Scala hay 2 maneras de invocar el foldLeft, y además hay una manera más fácil de calcular el factorial:

1 to 10 product

val lista = 1 to 10 toList
lista product
//foldLeft con lo que llamo la función "boobies"
lista.foldLeft(1)(_*_)
//o con la sintaxis más mafufa y la función "old boobies"
(1 /: lista) {_*_}

Ahora, en cuanto a recursividad... hace poco necesitaba implementar una función para convertir una cadena separada por espacios, en una lista. En Groovy por ejemplo puedo simplemente hacer "a b c d e".split() as List pero supongamos que quiero implementarla sin usar ninguna de las monerías que me ofrece el lenguaje. Hay dos maneras, y quiero pensar que ambas todavía son bastante optimizables:

//La manera iterativa
def toListI={ String s->
  List l=[]
  int i = s.indexOf(' ')
  while (i>0) {
    l+=s.substring(0, i)
    s=s.substring(i+1)
    i=s.indexOf(' ')
  }
  l+=s
  l
}

//La manera recursiva
def toListR={ String s ->
  int p=s.indexOf(' ')
  List rval = []
  if (p<0) {
    rval += s
  } else {
    rval += s.substring(0,p)
    rval += call(s.substring(p+1))
  }
  return rval
}

assert toListI("a b c d e") == toListR("a b c d e")

Lo que no me gusta de la versión recursiva es que estoy manejando una lista mutable. En Scala es más fácil manejar listas inmutables, por lo que la versión recursiva es más fácil de implementar, y además se puede implementar de modo que se utilice la optimización de tail recursion que mencionó Oscar:

def toList(s:String):List[String]={
  val p=s.indexOf(' ')
  if (p<0) {
    s::Nil
  } else {
    s.substring(0,p)::toList(s.substring(p+1))
  }
}

Pero esta implementación es engañosa; es puramente recursiva. Parece que el compilador podría aplicar la optimización de tail recursion que mencionaba Oscar, pero no es así, porque la última llamada en la función no es a toList, sino al método ::. Para que el compilador la convierta en implementación iterativa, necesitamos que toList sea la última invocación en la función. Esto se compila como un método iterativo, a pesar de que lo programé de manera recursiva:

def toList(s:String, l:List[String]):List[String]={
  val p=s.lastIndexOf(' ')
  if (p<0) {
    return s::l
  }
  toList(s.substring(0,p),s.substring(p+1)::l)
}

Esto es muy útil porque efectivamente hay algoritmos que se expresan mejor de manera recursiva, y pues el compilador nos puede ayudar a que se ejecuten de manera iterativa.