Rekursiva funktioner: Nyckelordet rec

Nyckelordet rec används tillsammans med nyckelordet let för att definiera en rekursiv funktion.

Syntax

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

Anmärkningar

Rekursiva funktioner – funktioner som anropar sig själva – identifieras explicit i språket F# med nyckelordet rec . Nyckelordet rec gör namnet på bindningen let tillgängligt i dess brödtext.

I följande exempel visas en rekursiv funktion som beräknar det n^:e Fibonacci-talet med hjälp av den matematiska definitionen.

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

Anmärkning

I praktiken är kod som föregående exempel inte idealisk eftersom den i onödan omberäknar värden som redan har beräknats. Detta beror på att det inte är tail rekursivt, vilket förklaras ytterligare i den här artikeln.

Metoderna är implicit rekursiva inom den typ som de definieras i, vilket innebär att det inte finns något behov av att lägga till nyckelordet rec . Till exempel:

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

let bindningar inom klasser är dock inte implicit rekursiva. Alla let-bundna funktioner kräver nyckelordet rec .

Rekursion av stjärt

För vissa rekursiva funktioner är det nödvändigt att omstrukturera en mer "ren" definition till en som är rekursiv. Detta förhindrar onödiga omkomputationer. Till exempel kan den tidigare Fibonacci-talgeneratorn skrivas om så här:

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Att generera ett Fibonacci-tal är ett bra exempel på en "naiv" algoritm som är matematiskt ren men ineffektiv i praktiken. Även om detta är en mer komplicerad implementering gör flera aspekter det effektivt i F# samtidigt som det fortfarande är rekursivt definierat:

• En rekursiv inre funktion med namnet loop, som är ett idiomatiskt F#-mönster.
• Två ackumulatorparametrar som skickar ackumulerade värden till rekursiva anrop.
• En kontroll av n värdet för att returnera en specifik ackumulator.

Om det här exemplet skrevs iterativt med en loop skulle koden se ut ungefär så att två olika värden ackumulerar tal tills ett visst villkor har uppfyllts.

Anledningen till att detta är tail-rekursivt är att det rekursiva anropet inte behöver spara några värden i anropsstacken. Alla mellanliggande värden som beräknas ackumuleras via indata till den inre funktionen. Detta gör också att F#-kompilatorn kan optimera koden så att den blir lika snabb som om du hade skrivit något som liknar en while loop.

Det är vanligt att skriva F#-kod som rekursivt bearbetar något med en inre och yttre funktion, vilket visas i föregående exempel. Den inre funktionen använder tail rekursion, medan den yttre funktionen har ett bättre gränssnitt för anropare.

Från och med F# 8.0 kan du använda TailCall attributet för att uttryckligen ange din avsikt att definiera en tail-rekursiv funktion för kompilatorn. Kompilatorn varnar dig sedan om din funktion gör icke-tail rekursiva anrop. Du kan använda attributet för metoder och funktioner på modulnivå.
Du kan till exempel använda den i den första fib definitionen:

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

skulle utlösa kompilatorvarningar om de två rekursiva anropen som inte är tail-rekursiva.

Ömsesidigt rekursiva funktioner

Ibland är funktioner ömsesidigt rekursiva, vilket innebär att anrop bildar en cirkel, där en funktion anropar en annan som i sin tur anropar den första, med valfritt antal anrop däremellan. Du måste definiera sådana funktioner tillsammans i en let bindning med hjälp av nyckelordet and för att länka ihop dem.

I följande exempel visas två ömsesidigt rekursiva funktioner.

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

Rekursiva värden

Du kan också definiera att ett let-bound-värde ska vara rekursivt. Detta görs ibland för loggning. Med F# 5 och nameof funktionen kan du göra följande:

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

Se även

• Funktioner