El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Funcions Recursives

Següent ►
►

Introducció

Les funcions recursives són aquelles que es criden a si mateixes per resoldre un problema. Aquest tipus de funcions són molt útils per a problemes que es poden dividir en subproblemes més petits del mateix tipus. En aquest tema, aprendrem què són les funcions recursives, com es defineixen en ALGOL, i veurem alguns exemples pràctics.

Conceptes Clau

  • Recursivitat: La capacitat d'una funció per cridar-se a si mateixa.
  • Cas Base: La condició que atura la recursivitat per evitar un bucle infinit.
  • Cas Recursiu: La part de la funció que inclou la crida recursiva.

Definició de Funcions Recursives en ALGOL

En ALGOL, les funcions recursives es defineixen de manera similar a les funcions normals, però inclouen una crida a si mateixes dins del seu cos. És crucial definir un cas base per evitar una recursió infinita.

Estructura Bàsica

procedure RecursiveFunction(parameters);
begin
    if (base_condition) then
        return base_value;
    else
        return RecursiveFunction(modified_parameters);
end;

Exemple Pràctic: Factorial d'un Nombre

El factorial d'un nombre n (denotat com n!) és el producte de tots els nombres enters positius fins a n. Es pot definir recursivament com:

  • 0! = 1 (cas base)
  • n! = n * (n-1)! (cas recursiu)

Implementació en ALGOL

procedure Factorial(n);
begin
    if n = 0 then
        return 1;
    else
        return n * Factorial(n - 1);
end;

begin
    print(Factorial(5));  // Sortida: 120
end;

Explicació del Codi

  1. Cas Base: Si n és 0, la funció retorna 1.
  2. Cas Recursiu: Si n no és 0, la funció retorna n multiplicat pel factorial de n-1.

Exemple Pràctic: Seqüència de Fibonacci

La seqüència de Fibonacci és una sèrie de nombres on cada nombre és la suma dels dos anteriors. Es pot definir recursivament com:

  • F(0) = 0 (cas base)
  • F(1) = 1 (cas base)
  • F(n) = F(n-1) + F(n-2) (cas recursiu)

Implementació en ALGOL

procedure Fibonacci(n);
begin
    if n = 0 then
        return 0;
    else if n = 1 then
        return 1;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
end;

begin
    print(Fibonacci(6));  // Sortida: 8
end;

Explicació del Codi

  1. Cas Base: Si n és 0, la funció retorna 0. Si n és 1, la funció retorna 1.
  2. Cas Recursiu: Si n és més gran que 1, la funció retorna la suma de Fibonacci(n-1) i Fibonacci(n-2).

Exercicis Pràctics

Exercici 1: Suma de Nombres Naturals

Escriu una funció recursiva en ALGOL que calculi la suma dels primers n nombres naturals.

Solució

procedure SumNaturals(n);
begin
    if n = 0 then
        return 0;
    else
        return n + SumNaturals(n - 1);
end;

begin
    print(SumNaturals(10));  // Sortida: 55
end;

Exercici 2: Potència d'un Nombre

Escriu una funció recursiva en ALGOL que calculi a^b (a elevat a la potència b).

Solució

procedure Power(a, b);
begin
    if b = 0 then
        return 1;
    else
        return a * Power(a, b - 1);
end;

begin
    print(Power(2, 3));  // Sortida: 8
end;

Errors Comuns i Consells

  • Oblidar el Cas Base: Assegura't sempre de definir un cas base per evitar una recursió infinita.
  • Modificació Incorrecta dels Paràmetres: Verifica que els paràmetres es modifiquen correctament en cada crida recursiva per assegurar que la funció convergeix cap al cas base.
  • Desbordament de la Pila: La recursivitat excessiva pot causar un desbordament de la pila. Considera utilitzar una solució iterativa si la profunditat de la recursió és massa gran.

Conclusió

Les funcions recursives són una eina poderosa en la programació, especialment per a problemes que es poden dividir en subproblemes més petits. En aquest tema, hem après com definir i utilitzar funcions recursives en ALGOL, i hem vist exemples pràctics com el càlcul del factorial i la seqüència de Fibonacci. Amb la pràctica, la recursivitat es convertirà en una tècnica valuosa en el teu repertori de programació.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats