recursive.md

tail recursive vs not tail recursive

not tail recursive

def fac( n: Int ): Int =
    if ( n == 0 ) 1
    else n * fac( n - 1 )

Diese Funktionen benötigen immer einen Stack, da der Aufrufbaum z.B. wie folgt aussieht:

fac(4)
    -> if ( 4 == 0  ) 1 else 4 * fac( 4 - 1 )
    -> 4 * fac( 3 )
    -> 4 * ( 3 * fac( 2 ) )
    -> 4 * ( 3 * ( 2 * fac( 1 ) ) )
    -> 4 * ( 3 * ( 2 * ( 1 * ( fac( 0 ) ) ) ) )
    -> 4 * ( 3 * ( 2 * ( 1 * ( 1 ) ) ) )

Der Stack wird benötigt um die Rekursionsstufen abzubilden. Somit muss der Wert für n immer auf dem Stack abgelegt werden. Hier kann es schnell zu einem Stack-Overflow kommen.

tail recursive

def fac( n: Int ): Int = {
     loop( acc, n): Int =
        if ( n == 0 ) 1
        else
            loop( a * n, n - 1 )
    loop( 1, n )
}

Definition: f(x₁,..., x_n) ... f(v₁,...,v_n)

Somit ist das Merkmal für eine tail recursive Funktion, dass die letzte Anweisung in der Funktion, ein rekursiver Aufruf ist. Der Vorteil von tail recursive Funktionen ist, dass diese keinen Stack benötigen. Der Compiler erkennt diese und sorgt dafür das der gleiche Speicher immer wieder verwendet wird. Somit können diese Funktionen quasi unendlich lange laufen, ohne einen Stack-Overflow zu verursachen.