# Frage zur Rekursion



## mucos001 (22. Dez 2019)

1                für n=1
   f(n-1)*f(n-1) +1      für n>1


   a)Programmieren Sie die Funktion f rekursiv in Java, so dass Sie eine Zeitkomplexität von O(2n) und eine Rekursionstiefe von O(n) besitzt.    

    public static int fRekursiv1(int n)
    {
        assert(n>=1);

        if(n==1)
        {
            return 1;
        }
        else
        {
            return fRekursiv1(n-1)*fRekursiv1(n-1)+1;
        }
    }

  b)Programmieren Sie die Funktion f rekursiv in Java, so dass Sie eine Zeitkomplexität von O(n) und eine Rekursionstiefe von O(n) besitzt.




c)Programmieren Sie die Funktion f iterativ in Java, so dass Sie eine Zeitkomplexität von O(n) besitzt. 
  Hinweis: Funktionen der Klasse Math dürfen nicht  benutzt werden




 Hallo Forum
 Nun hab ich die Aufgabe a gelöst.Weiß ich nicht Aufgabe b und c
 Könntet Ihr mir bitte helfen?
 danke


----------



## LimDul (22. Dez 2019)

Deine Aufgabenstellung stimmt nicht.

O(2n) ist das gleiche wie O(n). 

Und deine Lösung in a) hat nicht O(2n) sondern O(n²)  als Zeitkomplexität.


----------



## Meniskusschaden (22. Dez 2019)

LimDul hat gesagt.:


> O(2n) ist das gleiche wie O(n).


Ich denke, es war "2 hoch n" gemeint.


----------



## Meniskusschaden (22. Dez 2019)

mucos001 hat gesagt.:


> Weiß ich nicht Aufgabe b


Jeder Aufruf von fRekursiv1() zieht zwei weitere Aufrufe nach sich. Mit jeder Rekursionsebene verdoppelt sich also die Anzahl der Aufrufe. Wie könntest du die Formel denn verändern, damit nicht mehr zwei, sondern nur noch ein Aufruf nötig ist?


----------

