La recursència és un concepte fonamental en informàtica i matemàtiques que permet que les funcions s'autodevinguin, permetent la solució de problemes complexos mitjançant passos iteratius. Una representació visual que s'utilitza habitualment per entendre i analitzar l'execució de funcions recursives és un arbre de recursivitat. En aquest article, explorarem la teoria darrere dels arbres de recursivitat, la seva estructura i la seva importància per entendre els algorismes recursius.

Què és un arbre de recursivitat?

Un arbre de recursivitat és una representació gràfica que il·lustra el flux d'execució d'una funció recursiva. Proporciona un desglossament visual de les trucades recursives, mostrant la progressió de l'algorisme a mesura que es ramifica i, finalment, arriba a un cas base. L'estructura d'arbre ajuda a analitzar la complexitat del temps i entendre el procés recursiu implicat.

Estructura de l'arbre

Cada node d'un arbre de recursivitat representa una trucada recursiva particular. La trucada inicial està representada a la part superior, amb les trucades posteriors ramificant-se a sota. L'arbre creix cap avall, formant una estructura jeràrquica. El factor de ramificació de cada node depèn del nombre de trucades recursives realitzades dins de la funció. A més, la profunditat de l'arbre correspon al nombre de trucades recursives abans d'arribar al cas base.

escàner java a continuació

Cas base

El cas base serveix com a condició de terminació per a una funció recursiva. Defineix el punt en què s'atura la recursivitat i la funció comença a retornar valors. En un arbre de recursivitat, els nodes que representen el cas base se solen representar com a nodes fulla, ja que no donen lloc a més crides recursives.

Crides recursives

Els nodes fill d'un arbre de recursivitat representen les trucades recursives realitzades dins de la funció. Cada node fill correspon a una crida recursiva independent, donant lloc a la creació de nous subproblemes. Els valors o paràmetres passats a aquestes crides recursives poden diferir, donant lloc a variacions en les característiques dels subproblemes.

Flux d'execució:

Travessant un arbre de recursivitat proporciona informació sobre el flux d'execució d'una funció recursiva. A partir de la crida inicial al node arrel, seguim les branques per arribar a les trucades posteriors fins que ens trobem amb el cas base. A mesura que s'arriba als casos bàsics, les crides recursives comencen a tornar i els seus respectius nodes a l'arbre es marquen amb els valors retornats. El recorregut continua fins que s'ha travessat tot l'arbre.

Anàlisi de la complexitat temporal

Els arbres de recursivitat ajuden a analitzar la complexitat temporal dels algorismes recursius. Examinant l'estructura de l'arbre, podem determinar el nombre de trucades recursives realitzades i el treball realitzat a cada nivell. Aquesta anàlisi ajuda a entendre l'eficiència global de l'algorisme i a identificar les possibles ineficiències o oportunitats d'optimització.

Introducció

• Penseu en un programa que determina el factorial d'un nombre. Aquesta funció pren un nombre N com a entrada i retorna el factorial de N com a resultat. El pseudocodi d'aquesta funció s'assemblarà,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• La recursivitat s'exemplifica amb la funció que es va esmentar anteriorment. Estem invocant una funció per determinar el factorial d'un nombre. Aleshores, donat un valor menor del mateix nombre, aquesta funció s'anomena a si mateixa. Això continua fins que arribem al cas bàsic, en què no hi ha més trucades de funció.
• La recursència és una tècnica per manejar problemes complicats quan el resultat depèn dels resultats de casos més petits del mateix problema.
• Si pensem en funcions, es diu que una funció és recursiva si continua cridant-se a si mateixa fins que arriba al cas base.
• Qualsevol funció recursiva té dos components principals: el cas base i el pas recursiu. Deixem d'anar a la fase recursiva un cop arribem al cas bàsic. Per evitar la recursivitat sense fi, els casos bàsics s'han de definir correctament i són crucials. La definició de recursivitat infinita és una recursivitat que mai arriba al cas base. Si un programa mai arriba al cas base, el desbordament de la pila continuarà produint-se.

Tipus de recursivitat

En termes generals, hi ha dues formes diferents de recursivitat:

• Recursió lineal
• Recurs d'arbres
• Recursió lineal

Recursió lineal

• Es diu que una funció que s'anomena una vegada cada vegada que s'executa és recursiva lineal. Una bona il·lustració de la recursivitat lineal és la funció factorial. El nom 'recursivitat lineal' fa referència al fet que una funció lineal recursiva triga una quantitat de temps lineal a executar-se.
• Fes una ullada al pseudocodi següent:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Si mirem la funció doSomething(n), accepta un paràmetre anomenat n i fa alguns càlculs abans de tornar a cridar el mateix procediment però amb valors més baixos.
• Quan es crida al mètode doSomething() amb el valor de l'argument n, diguem que T(n) representa la quantitat total de temps necessari per completar el càlcul. Per a això, també podem formular una relació de recurrència, T(n) = T(n-1) + K. K serveix aquí com a constant. S'inclou la constant K perquè la funció necessita temps per assignar o desassignar memòria a una variable o realitzar una operació matemàtica. Utilitzem K per definir el temps ja que és tan minut i insignificant.
• La complexitat temporal d'aquest programa recursiu es pot calcular simplement ja que, en el pitjor escenari, el mètode doSomething() s'anomena n vegades. Formalment parlant, la complexitat temporal de la funció és O(N).

Recurs d'arbres

• Quan feu una crida recursiva al vostre cas recursiu més d'una vegada, s'anomena recursivitat en arbre. Una il·lustració efectiva de la recursivitat de l'arbre és la seqüència de Fibonacci. Les funcions recursives d'arbre operen en temps exponencial; no són lineals en la seva complexitat temporal.
• Fes una ullada al pseudocodi següent,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• L'única diferència entre aquest codi i l'anterior és que aquest fa una crida més a la mateixa funció amb un valor inferior de n.
• Posem T(n) = T(n-1) + T(n-2) + k com a relació de recurrència per a aquesta funció. K serveix com a constant una vegada més.
• Quan es realitza més d'una crida a la mateixa funció amb valors més petits, aquest tipus de recursivitat es coneix com a recursivitat en arbre. L'aspecte intrigant és ara: quant de temps consumeix aquesta funció?
• Feu una suposició basada en l'arbre de recursivitat que hi ha a continuació per a la mateixa funció.
  
• Se us pot passar pel cap que és un repte estimar la complexitat del temps mirant directament una funció recursiva, especialment quan es tracta d'una recursió d'arbre. El mètode de l'arbre de recursivitat és una de les diverses tècniques per calcular la complexitat temporal d'aquestes funcions. Examinem-ho amb més detall.

Què és el mètode de l'arbre de recursivitat?

• Les relacions de recurrència com T(N) = T(N/2) + N o les dues que hem tractat anteriorment a la secció de tipus de recursivitat es resolen mitjançant l'enfocament de l'arbre de recursivitat. Aquestes relacions de recurrència sovint utilitzen una estratègia de dividir i conquerir per abordar els problemes.
• Es necessita temps per integrar les respostes als problemes secundaris més petits que es creen quan un problema més gran es divideix en problemes secundaris més petits.
• La relació de recurrència, per exemple, és T(N) = 2 * T(N/2) + O(N) per a l'ordenació Merge. El temps necessari per combinar les respostes a dos subproblemes amb una mida combinada de T(N/2) és O(N), que també és cert a nivell d'implementació.
• Per exemple, com que la relació de recurrència per a la cerca binària és T(N) = T(N/2) + 1, sabem que cada iteració de la cerca binària dóna com a resultat un espai de cerca que es redueix a la meitat. Un cop determinat el resultat, sortim de la funció. La relació de recurrència s'ha afegit +1 perquè es tracta d'una operació de temps constant.
• La relació de recurrència T(n) = 2T(n/2) + Kn és una a considerar. Kn denota la quantitat de temps necessària per combinar les respostes a subproblemes n/2-dimensionals.
• Representem l'arbre de recursivitat per a la relació de recurrència esmentada anteriorment.

Podem treure algunes conclusions de l'estudi de l'arbre de recursivitat anterior, inclòs

1. La magnitud del problema a cada nivell és tot el que importa per determinar el valor d'un node. La mida del problema és n al nivell 0, n/2 al nivell 1, n/2 al nivell 2, etc.

2. En general, definim l'alçada de l'arbre igual a log (n), on n és la mida del problema, i l'alçada d'aquest arbre de recursivitat és igual al nombre de nivells de l'arbre. Això és cert perquè, com acabem d'establir, les relacions de recurrència utilitzen l'estratègia de dividir i conquerir per resoldre problemes, i passar de la mida del problema n a la mida del problema 1 només requereix fer passos de registre (n).

• Considereu, per exemple, el valor de N = 16. Si ens permet dividir N per 2 a cada pas, quants passos es necessiten per obtenir N = 1? Tenint en compte que estem dividint per dos a cada pas, la resposta correcta és 4, que és el valor de log(16) base 2.

log(16) base 2

log(2^4) base 2

4 * log(2) base 2, ja que log(a) base a = 1

per tant, 4 * log(2) base 2 = 4

3. A cada nivell, el segon terme de la recurrència es considera com l'arrel.

Tot i que la paraula 'arbre' apareix en el nom d'aquesta estratègia, no cal ser un expert en arbres per entendre-la.

Com utilitzar un arbre de recursivitat per resoldre relacions de recurrència?

El cost del subproblema a la tècnica de l'arbre de recursivitat és la quantitat de temps necessària per resoldre el subproblema. Per tant, si observeu la frase 'cost' enllaçada amb l'arbre de recursivitat, simplement es refereix a la quantitat de temps necessària per resoldre un determinat subproblema.

Entendrem tots aquests passos amb alguns exemples.

Exemple

Considereu la relació de recurrència,

T(n) = 2T(n/2) + K

Solució

La relació de recurrència donada mostra les propietats següents,

Un problema de mida n es divideix en dos subproblemes de mida n/2 cadascun. El cost de combinar les solucions d'aquests subproblemes és K.

Cada mida del problema de n/2 es divideix en dos subproblemes cadascun de mida n/4 i així successivament.

En l'últim nivell, la mida del subproblema es reduirà a 1. En altres paraules, finalment arribem al cas base.

Seguim els passos per resoldre aquesta relació de recurrència,

Estats Units quantes ciutats

Pas 1: dibuixeu l'arbre de recursivitat

Pas 2: calculeu l'alçada de l'arbre

Com que sabem que quan dividim contínuament un nombre per 2, arriba un moment en què aquest nombre es redueix a 1. Igual que amb la mida del problema N, suposem que després de K divisions per 2, N esdevé igual a 1, la qual cosa implica, ( n / 2^k) = 1

Aquí n / 2^k és la mida del problema a l'últim nivell i sempre és igual a 1.

Ara podem calcular fàcilment el valor de k a partir de l'expressió anterior agafant log() als dos costats. A continuació hi ha una derivació més clara,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) base 2

Per tant, l'alçada de l'arbre és log (n) base 2.

Pas 3: calculeu el cost a cada nivell

• Cost al Nivell-0 = K, es fusionen dos subproblemes.
• Cost al Nivell-1 = K + K = 2*K, dos subproblemes es fusionen dues vegades.
• Cost al nivell-2 = K + K + K + K = 4*K, dos subproblemes es fusionen quatre vegades. etcètera....

Pas 4: calcula el nombre de nodes a cada nivell

Primer determinem el nombre de nodes de l'últim nivell. De l'arbre de recursivitat, podem deduir-ho

• El nivell 0 té 1 (2^0) node
• El nivell 1 té 2 (2^1) nodes
• El nivell 2 té 4 (2^2) nodes
• El nivell 3 té 8 (2^3) nodes

Per tant, el nivell log(n) hauria de tenir 2^(log(n)) nodes, és a dir, n nodes.

Pas 5: suma el cost de tots els nivells

• El cost total es pot escriure com,
• Cost total = Cost de tots els nivells excepte l'últim nivell + Cost de l'últim nivell
• Cost total = Cost del nivell-0 + Cost del nivell-1 + Cost del nivell-2 +... + Cost del nivell-log(n) + Cost del darrer nivell

El cost de l'últim nivell es calcula per separat perquè és el cas base i no es fa cap fusió a l'últim nivell, de manera que el cost per resoldre un sol problema en aquest nivell és un valor constant. Prenem-ho com a O (1).

Posem els valors a les fórmules,

• T(n) = K + 2*K + 4*K + .... + log(n)` vegades + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) vegades)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) vegades + O(n)

Si mireu de prop l'expressió anterior, forma una progressió geomètrica (a, ar, ar^2, ar^3 ...... temps infinit). La suma de GP ve donada per S(N) = a / (r - 1). Aquí hi ha el primer terme i r és la raó comuna.