Scribd
Hochladen
6 Ansichten10 Seiten

Rekursion in Java

Das Dokument behandelt die rekursive Programmierung, bei der eine Methode sich selbst aufruft, und betont die Notwendigkeit einer Abbruchbedingung sowie die schrittweise Annäherung an diese. Es werden Beispiele wie die Fakultätsberechnung und die Fibonacci-Folge angeführt, um rekursive Algorithmen zu veranschaulichen. Zudem wird ein rekursiver Ansatz zur Multiplikation zweier Zahlen vorgestellt.

Hochgeladen von

bzb0z6c5m
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen
6 Ansichten10 Seiten

Rekursion in Java

Das Dokument behandelt die rekursive Programmierung, bei der eine Methode sich selbst aufruft, und betont die Notwendigkeit einer Abbruchbedingung sowie die schrittweise Annäherung an diese. Es werden Beispiele wie die Fakultätsberechnung und die Fibonacci-Folge angeführt, um rekursive Algorithmen zu veranschaulichen. Zudem wird ein rekursiver Ansatz zur Multiplikation zweier Zahlen vorgestellt.

Hochgeladen von

bzb0z6c5m
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen

Rekursion

SEW Rekursion Seite 1


Rekursion

Bei der rekursiven Programmierung ruft sich eine Methode


(Prozedur oder Funktion) selbst wieder auf.

main()

return 4
callMe(1)

return 4
callMe(2)

return 4
callMe(3)

return count
callMe(4)

SEW Rekursion Seite 2


Rekursion

Wesentliche Merkmale rekursiver Programmierung:

• Abbruchbedingung!

• Man soll sich in jeder Rekursionsstufe mehr der


Abbruchbedingung nähern - das zu lösende
Problem soll kleiner werden.

SEW Rekursion Seite 3


Beispiel 1: Fakultätsberechnung

Die Fakultät (auch Faktorielle genannt) ist eine mathematische


Funktion:
Fakultät(n) = 1 * 2 * ... * n
Fakultät(0) = 1
Beispiel:
5! = 1 * 2 * 3 * 4 * 5 = 120
4! = 1 * 2 * 3 * 4
3! = 1 * 2 * 3
oder
5! = 4! * 5
4! = 3! * 4
4
3! = 2! * 3
2! = ??? 1! = ??? 0! = 1
SEW Rekursion Seite 4
Faktorielle: Iterative Lösung

Die Methode „factorial“ ermittelt zum Parameter „n“ das Produkt


aller Zahlen zwischen 1 und n.

SEW Rekursion Seite 5


Faktorielle: Rekursiver Ansatz

Beispiel: 75! = 75 * 74 * 73 * …. * 2 * 1
75! = 75 * 74!

74! = 74 * 73 * 72 * … * 2 * 1
74! = 74 * 73!

Rekursive Definition:
factorial(n) := n * factorial(n-1) für n > 0 => Abstieg
factorial(0) := 1 => Ausstieg

SEW Rekursion Seite 6


Faktorielle: Rekursive Lösung

Aufgabe:
Entwirf den rekursiven Algorithmus für die Methode
long factorial(int n)

SEW Rekursion Seite 7


Faktorielle Rekursiv: Ablauf

Beispiel: 4! = 4 * 3 * 2 * 1 = 24

Main()

return 4 * 6
factorial(4)

return 3 * 2
factorial(3)

return 2 * 1
factorial(2)

return 1 * 1
factorial(1)

return 1
factorial(0)

SEW Rekursion Seite 8


Beispiel 2: Multiplikation

Aufgabe:
• Entwirf einen rekursiven Algorithmus
für die Multiplikation zweier
Operanden a und b.
• Dabei soll der Operand b a-Mal mit
sich selbst addiert werden.

11

SEW Rekursion Seite 11


Beispiel 3: Fibonacci-Folge

Aufgabe:
Entwirf den rekursiven Algorithmus für die
Methode

SEW Rekursion Seite 12

Das könnte Ihnen auch gefallen