Rekursionsbaum

[ChrisWest]

Hallo,
gegeben ist folgende rekursive Java Methode:

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?

 

[httpdigest]

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:

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?