Algorisme recursiu
Un algorisme recursiu és aquell que fa ús de la recursivitat. En la pràctica, és un algorisme implementat en una funció que es crida a si mateixa. Li cal una condició de parada per a no entrar en un bucle infinit. Alguns algorismes recursius es poden reescriure com algorismes iteratius.
Alguns exemples de recursivitat:
- En un text:
- Per a saber què és la recursivitat, primer s'ha de saber què és la recursivitat.
- En un acrònim:
- Què és GNU? → GNU No és Unix.
- Què és PHP? → PHP: Hipertext Preprocessor
- En matemàtiques:
- f(x) = x * f(x-1)
- En un algorisme:
- El càlcul del factorial d'un nombre es pot implementar amb un algorisme recursiu. En pseudocodi és:
FUNCIÓ F := FACTORIAL (SENCER:N) SI N = 0 F := 1 SINÓ F := N * FACTORIAL (N - 1) FI_SI FI_FUNCIÓ
És a dir: El factorial de zero val 1; per a nombres més grans que zero, el factorial del nombre és aquest mateix nombre multiplicat pel factorial del nombre sencer immediatament més petit.