La recursivitat és un concepte fonamental en la programació funcional i és àmpliament utilitzada en F#. En aquest tema, aprendrem què és la recursivitat, com utilitzar-la en F#, i veurem alguns exemples pràctics. També discutirem els avantatges i desavantatges de la recursivitat i com evitar problemes comuns com la recursivitat infinita.

La recursivitat és una tècnica de programació on una funció es crida a si mateixa per resoldre un problema. Un problema es divideix en subproblemes més petits, i la funció recursiva es crida a si mateixa per resoldre aquests subproblemes fins que s'arriba a un cas base, que és una condició que atura la recursió.

1. Cas Base: La condició que atura la recursió.
2. Cas Recursiu: La part de la funció que crida a si mateixa.

El factorial d'un nombre n (denotat com n!) és el producte de tots els nombres enters positius menors o iguals a n. Per exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120.

• Cas Base: Si n és 0, retornem 1.
• Cas Recursiu: Si n no és 0, retornem n multiplicat pel factorial de n - 1.

La seqüència de Fibonacci és una sèrie de nombres on cada nombre és la suma dels dos anteriors. Els primers dos nombres de la seqüència són 0 i 1.

• Cas Base: Si n és 0, retornem 0. Si n és 1, retornem 1.
• Cas Recursiu: Si n no és 0 ni 1, retornem la suma de fibonacci (n - 1) i fibonacci (n - 2).

• Claredat: Les solucions recursives poden ser més fàcils d'entendre i escriure.
• Divisió de Problemes: És ideal per a problemes que es poden dividir en subproblemes més petits.

• Eficiència: Les funcions recursives poden ser menys eficients que les iteratives, especialment si no es fa servir la recursivitat de cua.
• Recursivitat Infinita: Si no es defineix correctament el cas base, la funció pot cridar-se infinitament, causant un desbordament de la pila.

La recursivitat de cua és una forma especial de recursivitat on la crida recursiva és l'última operació que es fa en la funció. Això permet que el compilador optimitzi la recursió, evitant desbordaments de la pila.

• Cas Base: Si n és 0, retornem l'acumulador acc.
• Cas Recursiu: Multipliquem l'acumulador acc per n i cridem loop amb n - 1.

Escriu una funció recursiva que calculi la suma dels primers n nombres enters positius.

Escriu una funció recursiva de cua que calculi el n-è nombre de Fibonacci.

La recursivitat és una eina poderosa en la programació funcional que permet resoldre problemes complexos de manera elegant. Hem vist com implementar funcions recursives en F#, incloent-hi la recursivitat de cua per millorar l'eficiència. Practicar amb exercicis recursius t'ajudarà a comprendre millor aquest concepte i a aplicar-lo en situacions reals.