Funcții recursive

O funcție recursivă este o funcție care se apelează pe sine însăși. Funcțiile recursive reprezintă un instrument puternic pentru manipularea structurilor de date recursive, cum ar fi diversele arbori.

De exemplu, să definim o funcție care calculează factorialul unui număr, utilizând o abordare recursivă:

package main
 
import "fmt"
 
func factorial(n uint) uint{
 
    if n == 0{
        return 1
    }
    return n * factorial(n - 1)
}

func main() {
     
    fmt.Println(factorial(4))   // 24
    fmt.Println(factorial(5))   // 120
    fmt.Println(factorial(6))   // 720
}

Aici, funcția factorial primește un anumit număr pozitiv pentru care trebuie să calculeze factorialul. Rezultatul obținut este returnat din funcție. La început, se verifică condiția ca, dacă numărul este 0, funcția returnează 1. Altfel, funcția returnează produsul numărului n cu rezultatul aceleași funcții pentru n-1.

Atunci când creăm o funcție recursivă, aceasta trebuie să aibă neapărat un caz de bază, care folosește operatorul return și se află la începutul funcției. În cazul factorialului, acest caz de bază este if x == 0 {return 1}.

În plus, toate apelurile recursive trebuie să se refere la subfuncții, care, în final, vor ajunge la cazul de bază. Astfel, atunci când se transmite o valoare pozitivă funcției, în apelurile recursive succesive ale subfuncțiilor se va transmite de fiecare dată o valoare mai mică cu 1. La final, vom ajunge la situația în care numărul va fi 0 și se va utiliza cazul de bază.

De exemplu, apelul factorial(4) poate fi detaliat astfel:

factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)
4 * 3 * 2 * 1 * 1

Un alt exemplu clasic de funcție recursivă este funcția care calculează numerele Fibonacci. Al n-lea membru al secvenței Fibonacci este determinat de formula: f(n) = f(n-1) + f(n-2), unde f(0) = 0 și f(1) = 1.

package main
 
import "fmt"
 
func fibbonachi(n uint) uint{
     
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fibbonachi(n - 1) + fibbonachi(n - 2)
}

func main() {
     
    fmt.Println(fibbonachi(4))  // 3
    fmt.Println(fibbonachi(5))  // 5
    fmt.Println(fibbonachi(6))  // 8
}