Programmieren mit Harald R. Haberstroh

Betrachten Sie folgendes Beispiel:

 1:/**
 2: * java-stoff: speicher.Fib.java
 3: * 
 4: * 16.12.2009, Harald R. Haberstroh
 5: */
 6:package speicher;
 7:
 8:import java.util.Scanner;
 9:
10:/**
11: * Fibonacci-Zahlen zur demo des Aufrufstacks.
12: *
13: * @author Harald R. Haberstroh (hp)
14: *
15: */
16:public class Fib {
17:
18:  public static int fib(int n) {
19:    int ret = 1;
20:    if (n < 0) {
21:      throw new IllegalArgumentException("n muss größer oder gleich Null sein");      
22:    }
23:    if (n > 1) {
24:      ret = fib(n-1) + fib(n-2);
25:    }
26:    return ret;
27:  }
28:  /**
29:   * @param args
30:   */
31:  public static void main(String[] args) {
32:    Scanner in = new Scanner(System.in);
33:    int n = 0;
34:    int f = 0;
35:    while (in.hasNextInt()) {
36:      n = in.nextInt();
37:      f = fib(n);
38:      System.out.printf("fib(%d) = %d\n", n, f);
39:    }
40:  }
41:}

Uns interessiert die Funktionsweise der Aufrufs der rekursiven Funktion fib(). Arbeiten Sie das Programm am Papier ab. Beginnen Sie mit Zeile 37 und dem Wert n = 5. Skizzieren Sie den Aufrufstack, wenn Sie in Zeile 26 angelangt sind.

Bedenken Sie, dass bei den meisten Aufrufen von fib() zwei rekursive Aufrufe stattfinden, die ihrerseits wieder zwei rekursive Aufrufe tätigen usw. Das Bild zeigt die Aufrufe für n = 5:

Labels: allgemeines, Aufgabe, Java, PR2

# Eingestellt von Harald R. Haberstroh @ 13:05