Rekursionsbaum

Bitte aktiviere JavaScript!
Hallo,
gegeben ist folgende rekursive Java Methode:

Java:
void fun(int arr[], int l, int x){
if (l > arr.length-1){
System.out.println(x);
return;
}
fun(arr, l+1, x+arr[l]);
fun(arr, l+1, x);
}
Aufgabe:
1) Geben Sie den Rekursionsbaum sowie die Ausgabe des Aufrufs fun(a,0,0) für a={5,4,3} an.
Ausgabe = 12,9,8,5,7,4,3,0 aber wie gebe ich den Rekursionsbaum an, das habe ich leider nicht verstanden, kann mir das jemand ein Tipp geben oder kennt ihr eine gute Seite?
2) Was berechnet die Methode für ein beliebiges Array a, wenn Sie mit fun(a,0,0) aufgerufen wird? Begründen Sie Ihre Antwort.
Ideen?
 
A

Anzeige




Vielleicht hilft dir unser Kurs hier weiter —> (hier klicken)
aber wie gebe ich den Rekursionsbaum an, das habe ich leider nicht verstanden
Du gehst halt einfach die rekursiven Aufrufe durch. Überall dort, wo ein Aufruf in dem Callstack stattfindet, machst du eine weitere Kante in dem Baum und benennst den Baumknoten etwa so wie die aktuellen Argumente, mit denen die Methode dort aufgerufen wird:
Code:
fun([5,4,3], 0, 0)
|-> fun(..., 1, 5)
|   |-> fun(..., 2, 9)
|   |   |-> fun(..., 3, 12)
|   |   \-> fun(..., 3, 9)
|   \-> fun(..., 2, 5)
|       |-> fun(..., 3, 8)
|       \-> fun(..., 3, 5)
\-> fun(..., 1, 0)
    |-> fun(..., 2, 4)
    |   |-> fun(..., 3, 7)
    |   \-> fun(..., 3, 4)
    \-> fun(..., 2, 0)
        |-> fun(..., 3, 3)
        \-> fun(..., 3, 0)
EDIT: Bezüglich was die Funktion berechnet bzw. ausgibt: Hat was mit der arithmetischen Summe und der Potenzmenge zu tun. Schau mal, was die Funktion pro Schritt tut. Sie "addiert" ein Arrayelement im ersten rekursiven Abstieg und überspringt dieses Arrayelement im zweiten rekursiven Abstieg. Wenn man das pro Rekursionstiefe tut, hat man im Endeffekt was genau getan?
 
Zuletzt bearbeitet:
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben