Entenent recursió amb JavaScript

Introducció

Alguns problemes es resolen de forma més natural usant recursió. Per exemple, una seqüència com la de Fibonacci té una definició recursiva. Cada número en ella és la suma dels dos nombres anteriors de la seqüència. Els problemes que requereixen que construeixis o que recorris una estructura de dades de tipus arbre també poden ser resolts amb recursió. Entrenar-te per pensar recursivament et donarà una poderosa habilitat per abordar aquests problemes.

En aquest tutorial faré una revisió pas a pas de diverses funcions recursives per veure com funcionen i mostrar tècniques que pots utilitzar per definir funcions recursives sistemàticament.

Contingut:

• Què és la recursió?
• recursió amb nombres
• recursió amb llistes
• Construint llistes
• repàs

què és la recursió?

Una funció definida recursivament és una funció que es defineix en termes d’una versió més senzilla de si mateixa. Aquest és un exemple simplificat:

function doA(n) { ... doA(n-1);}

Per comprendre com funciona la recursió conceptualment, veurem un exemple que no té res a veure amb codi. Imagina que ets el responsable de respondre les trucades telefòniques en el teu treball. Atès que aquesta és una empresa ocupada, el teu telèfon té múltiples línies perquè puguis atendre múltiples trucades a el mateix temps. Cada línia telefònica és un botó en el receptor, i quan hi hagi una trucada entrant el botó canviarà. Avui, quan arribes a la feina i encens el telèfon, hi ha quatre línies parpellejant a el mateix temps. Per tant et poses a treballar responent totes les trucades.

Contestes la línia un i dius “si us plau esperi”. Després contestes la línia dos i la poses en espera. A continuació contestes la línia 3 i la poses en espera. Finalment, contestes la quarta línia i parles amb la persona que està trucant. A l’acabar amb la quarta persona penges i contestes la tercera trucada. A l’acabar amb la tercera crida, penges i contestes la segona. A l’acabar amb la segona trucada, penges i contestes la primera. Quan acabes amb aquesta trucada finalment pots penjar el telèfon.

Cadascuna de les trucades telefòniques d’aquest exemple és com una crida recursiva en una funció. Quan reps una trucada, aquesta es col·loca a la pila de trucades (en termes de codi). Si no pots acabar una trucada immediatament llavors la col·loques en espera. Si tens una crida a una funció que no pot ser avaluada immediatament, aquesta es queda a la pila de trucades. Quan pots contestar una trucada, aquesta és atesa. Quan el teu codi és capaç d’avaluar la crida a una funció, aquesta es treu de la pila. Tingues aquesta analogia en ment mentre revises els següents exemples de codi.

Recursió amb nombres

Totes les funcions recursives necessiten un cas base per poder acabar. No obstant això, el simple fet d’afegir un cas base de la nostra funció no evitarà que aquesta s’executi infinitament. La funció ha de tenir un pas per apropar-nos a el cas base. Finalment hi ha el pas recursiu. En el pas recursiu, el problema es redueix a una versió més petita de el problema.

Suposem que tens una funció que sumarà els números de l’1 a n. Per exemple, si n = 4, la funció sumarà 1 + 2 + 3 + 4.

Primer vam determinar el cas base. Trobar el cas base és com trobar el cas en què el problema pot ser resolt sense recursió. En aquest exemple és quan n és igual a zero. Zero no té parts, de manera que la nostra recursió pot aturar-se a l’arribar a 0.

A cada pas restaràs el valor un a el nombre actual. Quin és el cas recursiu? El cas recursiu és la funció suma invocada amb el nombre reduït.

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

Això és el que passa en cada pas:

• Aneu a sum (4).
• 4 és igual a 0? No. Col·loca a sum (4) en espera i veu a sum (3).
• 3 és igual a 0? No. Col·loca a sum (3) en espera i veu a sum (2).
• 2 és igual a 0? No. Col·loca a sum (2) en espera i veu a sum (1).
• 1 és igual a 0? No. Col·loca a sum (1) en espera i veu a sum (0).
• 0 és igual a 0? Sí. Avalua sum (0).
• Reprèn sum (1).
• Reprèn sum (2).
• Reprèn sum (3).
• Reprèn sum (4).

Aquesta és una altra forma de veure com és que la funció està processant cada trucada:

sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10

l’argument ha de canviar en el cas recursiu i acostar-te a el cas base. Aquest argument ha de verificar en el cas base. En l’exemple anterior, ja que estem restant el valor un en el cas recursiu hem de verificar si l’argument és igual a zero en el nostre cas base.

Tasca

1. Implementa la funció suma usant un cicle en comptes de recursió.
2. Crea una funció que multipliqui dos nombres de manera recursiva. Per exemple, multiply(2,4) donarà com a resultat 8. Escriu què passa durant cada pas per multiply(2,4).

recursió amb llistes

la recursió en una llista és similar a la recursió en un nombre, però en comptes de reduir el nombre en cada pas anem a reduir la llista en cada pas fins que tinguem una llista buida.

Considera la funció sum que rep una llista com a entrada i retorna la suma de tots els elements d’aquesta llista. Aquesta és una implementació per a la funció sum:

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

La funció empty retorna el valor true (vertader) si la llista no té elements. La funció car retorna el primer element de la llista. Per exemple, car() retorna el valor 1. La funció cdr retorna la llista sense el primer element. Per exemple, cdr() retorna. Què passa en executar sum()?

sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910

A l’executar la recursió en una llista es revisa si està buida. Altrament es porta a terme el pas recursiu en una versió reduïda de la llista.

Tasca

1. Torna a escriure aquesta funció sum de manera que usi un cicle per sumar cada element de la llista en comptes d’usar recursió.
2. Defineix una funció anomenada length (longitud) que rebi una llista com a entrada i retorni el nombre d’elements d’aquesta llista. No has de fer servir la funció length integrada en JavaScript. Per exemple, length() ha de tornar el valor 4. Escriu què passa a cada pas.

Construint llistes

Al últim exemple estàvem tornant un nombre. Però suposem que volem tornar una llista. Això vol dir que en comptes d’afegir un nombre al nostre pas recursiu, ens cal afegir una llista. Considera la funció remove (eliminar), que rep un element i una llista com a entrada i retorna la llista sense l’element que vulguem treure. Solament el primer element que trobem serà eliminat.

function remove(item, l){ if (empty(l)) { return ; } else if (eq(car(l), item)) { return cdr(l); } else { return cons(car(l), remove(item, cdr(l))); }}remove('c', ) //

Aquí, la funció eq retorna un valor true (vertader ) si ambdues entrades són iguals. La funció cons rep un element i una llista com entrades i retorna una nova llista amb l’element afegit a el principi de la mateixa.

Revisem si el primer element de la llista és igual a l’element que vulguem eliminar. Si és així, elimina el primer element de la llista i torna la llista nova. Si el primer element no és igual a l’element que vulguem eliminar, prenem el primer element de la llista i el afegim a el pas recursiu. El pas recursiu contindrà a la llista amb el primer element eliminat.

Seguirem eliminant elements fins que arribem al nostre cas base, que és una llista buida. Una llista buida vol dir que hem recorregut tots els seus elements. Què fa la funció remove('c', )?

remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )

En una situació en què necessitem construir una llista, prenem el primer element i el afegim a la part recursiva de la nostra llista.

Tasca

1. Torna a escriure la funció remove (eliminar) de manera que usi cicles en lloc de recursió per suprimir un element d’una llista.
2. Modifica la funció remove perquè elimini totes les ocurrències d’un element en una llista. Per exemple, remove(‘c’, retorna. Escriu què passa pas a pas.

Repàs

Una funció recursiva té tres parts. La primera és el cas base, que és la condició terminal. La segona és el pas que ens acosta al nostre cas base. La tercera és el pas recursiu, en el qual la funció s’invoca a si mateixa amb una entrada reduïda.

La recursió és com la iteració. Qualsevol funció que puguis definir recursivament també pot definir-se usant cicles. Altres aspectes a considerar a l’usar aquesta tècnica són la recursió en llistes niades i l’optimització de les teves trucades recursives.

Un gran recurs per continuar aprenent sobre recursió és el llibre The Little Schemer. Aquest t’ensenya a pensar recursivament usant un format de preguntes i respostes.