Entendiendo recursión con JavaScript

() translation by (you can also view the original English article)

Introducción

Algunos problemas se resuelven de forma más natural usando recursión. Por ejemplo, una secuencia como la de Fibonacci tiene una definición recursiva. Cada número en ella es la suma de los dos números anteriores de la secuencia. Los problemas que requieren que construyas o que recorras una estructura de datos de tipo árbol también pueden ser resueltos con recursión. Entrenarte para pensar recursivamente te dará una poderosa habilidad para abordar dichos problemas.

En este tutorial haré una revisión paso a paso de varias funciones recursivas para ver cómo funcionan y mostrarte técnicas que puedes usar para definir funciones recursivas sistemáticamente.

Contenido:

¿Qué es la recursión?
Recursión con números
Recursión con listas
Construyendo listas
Repaso

¿Qué es la recursión?

Una función definida recursivamente es una función que se define en términos de una versión más sencilla de sí misma. Este es un ejemplo simplificado:

1	function doA(n) {
2	...
3	doA(n-1);
4	}

Para comprender cómo funciona la recursión conceptualmente, veremos un ejemplo que no tiene nada que ver con código. Imagina que eres el responsable de responder las llamadas telefónicas en tu trabajo. Dado que esta es una empresa ocupada, tu teléfono tiene múltiples líneas para que puedas atender múltiples llamadas al mismo tiempo. Cada línea telefónica es un botón en el receptor, y cuando haya una llamada entrante el botón parpadeará. Hoy, cuando llegas al trabajo y enciendes el teléfono, hay cuatro líneas parpadeando al mismo tiempo. Por lo tanto te pones a trabajar respondiendo todas las llamadas.

Contestas la línea uno y dices "por favor espere". Luego contestas la línea dos y la pones en espera. A continuación contestas la línea tres y la pones en espera. Finalmente, contestas la cuarta línea y hablas con la persona que está llamando. Al terminar con la cuarta persona cuelgas y contestas la tercera llamada. Al terminar con la tercera llamada, cuelgas y contestas la segunda. Al terminar con la segunda llamada, cuelgas y contestas la primera. Cuando terminas con esa llamada finalmente puedes colgar el teléfono.

Cada una de las llamadas telefónicas de este ejemplo es como una llamada recursiva en una función. Cuando recibes una llamada, ésta se coloca en la pila de llamadas (en términos de código). Si no puedes terminar una llamada de inmediato entonces la colocas en espera. Si tienes una llamada a una función que no puede ser evaluada inmediatamente, ésta se queda en la pila de llamadas. Cuando puedes contestar una llamada, ésta es atendida. Cuando tu código es capaz de evaluar la llamada a una función, ésta se saca de la pila. Ten esta analogía en mente mientras revisas los siguientes ejemplos de código.

Recursión con números

Todas las funciones recursivas necesitan un caso base para poder terminar. Sin embargo, el simple hecho de añadir un caso base a nuestra función no evitará que ésta se ejecute infinitamente. La función debe tener un paso para acercarnos al caso base. Por último está el paso recursivo. En el paso recursivo, el problema se reduce a una versión más pequeña del problema.

Supongamos que tienes una función que sumará los números del 1 a n. Por ejemplo, si n = 4, la función sumará 1 + 2 + 3 + 4.

Primero determinamos el caso base. Encontrar el caso base es como encontrar el caso en el que el problema puede ser resuelto sin recursión. En este ejemplo es cuando n es igual a cero. Cero no tiene partes, por lo que nuestra recursión puede detenerse al llegar a 0.

En cada paso restarás el valor uno al número actual. ¿Cuál es el caso recursivo? El caso recursivo es la función suma invocada con el número reducido.

function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}

sum(4);     //10

Esto es lo que ocurre en cada paso:

Ve a sum(4).
¿4 es igual a 0? No. Coloca a sum(4) en espera y ve a sum(3).
¿3 es igual a 0? No. Coloca a sum(3) en espera y ve a sum(2).
¿2 es igual a 0? No. Coloca a sum(2) en espera y ve a sum(1).
¿1 es igual a 0? No. Coloca a sum(1) en espera y ve a sum(0).
¿0 es igual a 0? Sí. Evalúa sum(0).
Retoma sum(1).
Retoma sum(2).
Retoma sum(3).
Retoma sum(4).

Esta es otra forma de ver cómo es que la función está procesando cada llamada:

1	sum(4)
2	4 + sum(3)
3	4 + ( 3 + sum(2) )
4	4 + ( 3 + ( 2 + sum(1) ))
5	4 + ( 3 + ( 2 + ( 1 + sum(0) )))
6	4 + ( 3 + ( 2 + ( 1 + 0 ) ))
7	4 + ( 3 + ( 2 + 1 ) )
8	4 + ( 3 + 3 )
9	4 + 6
10	10

El argumento debe cambiar en el caso recursivo y acercarte al caso base. Este argumento debe verificarse en el caso base. En el ejemplo anterior, ya que estamos restando el valor uno en el caso recursivo debemos verificar si el argumento es igual a cero en nuestro caso base.

Tarea

Implementa la función suma usando un ciclo en vez de recursión.
Crea una función que multiplique dos números de forma recursiva. Por ejemplo, multiply(2,4) dará como resultado 8. Escribe qué ocurre durante cada paso para multiply(2,4).

Recursión con listas

La recursión en una lista es similar a la recursión en un número, pero en vez de reducir el número en cada paso vamos a reducir la lista en cada paso hasta que tengamos una lista vacía.

Considera la función sum que recibe una lista como entrada y devuelve la suma de todos los elementos de dicha lista. Esta es una implementación para la función sum:

function sum(l){
    if (empty(l)) {
        return 0;
    } else {
        return car(l) + sum(cdr(l));
    }
}

La función empty devuelve el valor true (verdadero) si la lista no tiene elementos. La función car devuelve el primer elemento de la lista. Por ejemplo, car([1,2,3,4]) devuelve el valor 1. La función cdr devuelve la lista sin el primer elemento. Por ejemplo, cdr([1,2,3,4]) devuelve [2,3,4]. ¿Qué pasa cuando ejecutamos sum([1,2,3,4])?

1	sum([1,2,3,4])
2	1 + sum([2,3,4])
3	1 + ( 2 + sum([3,4]) )
4	1 + ( 2 + ( 3 + sum([4]) ))
5	1 + ( 2 + ( 3 + ( 4 + sum([]) )))
6	1 + ( 2 + ( 3 + ( 4 + 0 ) ))
7	1 + ( 2 + ( 3 + 4 ) )
8	1 + ( 2 + 7 )
9	1 + 9
10	10

Al ejecutar la recursión en una lista se revisa si está vacía. De lo contrario se lleva a cabo el paso recursivo en una versión reducida de la lista.

Tarea

Vuelve a escribir esta función sum de manera que use un ciclo para sumar cada elemento de la lista en vez de usar recursión.
Define una función llamada length (longitud) que reciba una lista como entrada y devuelva el número de elementos de dicha lista. No debes usar la función length integrada en JavaScript. Por ejemplo, length(['a', 'b', 'c', 'd']) debe devolver el valor 4. Escribe qué ocurre en cada paso.

Construyendo listas

En el último ejemplo estábamos devolviendo un número. Pero supongamos que queremos devolver una lista. Esto significa que en vez de añadir un número a nuestro paso recursivo, necesitamos añadir una lista. Considera la función remove (eliminar), que recibe un elemento y una lista como entrada y devuelve la lista sin el elemento que queramos quitar. Solamente el primer elemento que encontremos será eliminado.

1	function remove(item, l){
2	if (empty(l)) {
3	return [];
4	} else if (eq(car(l), item)) {
5	return cdr(l);
6	} else {
7	return cons(car(l), remove(item, cdr(l)));
8	}
9	}
10
11	remove('c', ['a', 'b', 'c', 'd']) //[‘a’, ‘b’, ‘d’]

Aquí, la función eq devuelve un valor true (verdadero) si ambas entradas son iguales. La función cons recibe un elemento y una lista como entradas y devuelve una nueva lista con el elemento añadido al principio de la misma.

Revisamos si el primer elemento de la lista es igual al elemento que queramos eliminar. Si es así, elimina el primer elemento de la lista y devuelve la lista nueva. Si el primer elemento no es igual al elemento que queramos eliminar, tomamos el primer elemento de la lista y lo agregamos al paso recursivo. El paso recursivo contendrá a la lista con el primer elemento eliminado.

Vamos a seguir eliminando elementos hasta que lleguemos a nuestro caso base, que es una lista vacía. Una lista vacía significa que hemos recorrido todos sus elementos. ¿Qué hace la función remove('c', ['a', 'b', 'c', 'd'])?

1	remove('c', ['a', 'b', 'c', 'd'])
2	cons( ‘a’, remove(‘c’, [‘b’, ‘c’, ‘d’]) )
3	cons( ‘a’ , cons( ‘b’, remove(‘c’, [‘c’, ‘d’]) ))
4	cons( ‘a’, cons( ‘b’, [‘d’] )
5	cons( ‘a’, [‘b’, ‘d’])
6	[‘a’, ‘b’, ‘d’]

En una situación en la que necesitemos construir una lista, tomamos el primer elemento y lo agregamos a la parte recursiva de nuestra lista.

Tarea

Vuelve a escribir la función remove (eliminar) de manera que use ciclos en vez de recursión para eliminar un elemento de una lista.
Modifica la función remove para que elimine todas las ocurrencias de un elemento en una lista. Por ejemplo, remove(‘c’, [‘a’, ‘b’, ‘c’, ‘d’, ‘c’] devuelve [‘a’, ‘b’, ‘d’]. Escribe qué ocurre paso a paso.

Repaso

Una función recursiva tiene tres partes. La primera es el caso base, que es la condición terminal. La segunda es el paso que nos acerca a nuestro caso base. La tercera es el paso recursivo, en el que la función se invoca a sí misma con una entrada reducida.

La recursión es como la iteración. Cualquier función que puedas definir recursivamente también puede definirse usando ciclos. Otros aspectos a considerar al usar esta técnica son la recursión en listas anidadas y la optimización de tus llamadas recursivas.

Un gran recurso para continuar aprendiendo sobre recursión es el libro The Little Schemer. Éste te enseña a pensar recursivamente usando un formato de preguntas y respuestas.