Wie konvertiert man Rekursion in Tail Rekursion in diesem Beispiel?

Ich habe diese rekursive Funktion, um die Würfel von n geraden Zahlen hinzuzufügen, und ich möchte es nicht zu einer Tail-Rekursion machen.Wie konvertiert man Rekursion in Tail Rekursion in diesem Beispiel?

int sum_even_cubes_rec(int n) { 
if (n < 2) 
    return 0; 
if ((n % 2) == 0) { 
    return (n*n*n + sum_even_cubes_rec(n - 1)); 
} else { 
    return (0 + sum_even_cubes_rec(n - 1)); 
} 
}

Dies ist, was ich geschrieben habe, aber es ist falsch und ich weiß nicht, wie es zu beheben ist. Können Sie mir bitte helfen.

int sum_even_cubes_rec2(int n, int acc) { 
if ((n % 2) == 0) { 
    return sum_even_cubes_rec2 (n-1, acc + n*n*n); 
} return acc; 
} 

int sum_even_cubes_helperFunktion(int n) { 
return sum_even_cubes_rec2(n, 0); 
}

Quelle

2016-11-20 Ema

dieses Add 'if (n <2) return 0;' als erste Zeile in der Code und dies zu 'return sum_even_cubes_rec2 (n-1, acc);' als letzte Zeile und entfernen 'Rückkehr acc' aus Ihrem Code –

Ihre Vorgehensweise ist korrekt. Sie haben bereits das Argument acc hinzugefügt. Sie müssen also für den Basisfall zurückkehren.

Der Rest des Codes fast richtig ist - Sie müssen anpassen, was Sie acc für den nächsten Aufruf hinzu:

int sum_even_cubes_rec2(int n, int acc) { 
    if (n < 2) { 
     return acc; 
    } 
    int nextAcc = (n % 2) == 0 ? acc + n*n*n : acc; 
    return sum_even_cubes_rec2 (n-1, nextAcc); 
}

Quelle

2016-11-20 12:34:44 dasblinkenlight

... und jetzt, dass Sie Tail-Rekursion haben, können Sie oder der Compiler es in eine Schleife (Beseitigung der rekursiven Aufrufe) verwandeln. –

einfach kann es als dieser

int sum_even_cubes_rec2(int n) { 
     static int ans = 0; 
     if(n<2){ 
     int tmp =ans; 
     ans =0; 
     return tmp; 
     } 
     ans += ((n%2==0)? n*n*n : 0); 
     return sum_even_cubes_rec2(n-1); 
}

geschrieben werden

Quelle

2016-11-20 12:35:56

Ja, jetzt ist das eine Tail-Recursion-Funktion, aber es funktioniert nur beim ersten Mal, wenn Sie es ausführen. Ab dem zweiten Mal gibt es falsche Ergebnisse zurück, weil es ein 'static' verwendet. – dasblinkenlight

int sum_even_cubes(int n) { 
    int ret =0; 

    if (n < 2) return 0; 

    ret = (n % 2) ? 0: n*n*n; 
    return ret + sum_even_cubes(n-1); 
}

Gcc -O2 -S kompiliert dies in (Funktionsargument ist %edi; Rückgabewert ist in %eax; Ziel für die Rekursion-Schleife ist .L4):

sum_even_cubes: 
.LFB0: 
     .cfi_startproc 
     xorl %eax, %eax 
     cmpl $1, %edi 
     jle  .L5 
     .p2align 4,,10 
     .p2align 3 
.L4: 
     xorl %edx, %edx 
     testb $1, %dil 
     jne  .L3 
     movl %edi, %edx 
     imull %edi, %edx 
     imull %edi, %edx 
.L3: 
     subl $1, %edi 
     addl %edx, %eax 
     cmpl $1, %edi 
     jne  .L4 
     rep ret 
.L5: 
     rep ret 
     .cfi_endproc 
.LFE0:

Quelle

2016-11-20 13:58:59 wildplasser

Wie konvertiert man Rekursion in Tail Rekursion in diesem Beispiel?

Antwort

Verwandte Themen