M3 - Programació estructurada / Continguts UF2: Recursivitat

Introducció

Els programes que hem vist fins ara estan estructurats generalment com a mètodes que es criden entre si, d'una manera disciplinada i jeràrquica. No obstant això, per a alguns problemes és convenient fer que un mètode es cridi a si mateix. Aquest mètode es coneix com a mètode recursiu; aquest mètode es pot cridar en forma directa o indirecta a través d'un altre mètode.

Conceptes de recursivitat

Els mètodes per solucionar problemes recursius tenen diversos elements en comú. Quan es fa una crida a un mètode recursiu per resoldre un problema, el mètode en realitat és capaç de resoldre només el (els) cas(os) més simple(s), o cas(os) base. Si es fa la crida al mètode amb un cas base, el mètode retorna un resultat. Si es fa la crida al mètode amb un problema més complex, el mètode comunament divideix el problema en dues peces conceptuals: una peça que el mètode sap com resoldre i una altra peça que no sap com resoldre. Perquè la recursivitat sigui factible, aquesta última peça ha de ser similar al problema original, però una versió lleugerament més senzilla o simple del mateix. A causa que aquest nou problema s'assembla al problema original, el mètode crida a una nova còpia de si mateix per treballar en el problema més petit; a això se li coneix com crida recursiva, i també com a pas recursiu. En general, el pas recursiu inclou una instrucció return, ja que el seu resultat es combina amb la part del problema que el mètode va saber com resoldre, per formar un resultat que es passarà de tornada al mètode original que va fer la crida. Aquest concepte de separar el problema en dues porcions més petites és una forma del mètode “divideix i venceràs”.

El pas recursiu s'executa mentre segueixi activa la crida original al mètode (és a dir, que no hagi acabat la seva execució). Es poden produir moltes crides recursives més, a mesura que el mètode divideix cada nou subproblema en dues peces conceptuals. Perquè la recursivitat acabi en un moment donat, cada vegada que el mètode es crida a si mateix amb una versió més simple del problema original, la seqüència de problemes cada vegada més petits ha de convergir en un cas base. En aquest punt, el mètode reconeix el cas base i retorna un resultat a la còpia anterior del mètode. Després s'origina una seqüència de tornades, fins que la crida al mètode original retorna el resultat final al mètode que el va cridar.