Rekursion ist ein Konzept in der Informatik und Mathematik, bei dem eine Funktion sich selbst aufruft, um eine Aufgabe zu lösen. Eine rekursive Funktion kann in kleinere Teilprobleme zerlegt werden, die dasselbe Problem, jedoch in einer kleineren Instanz, darstellen. Rekursion wird oft verwendet, um komplexe Probleme in einfachere, wiederholbare Schritte zu zerlegen.
In rekursiven Funktionen gibt es normalerweise zwei Hauptbestandteile:
Rekursiver Fall: Der rekursive Fall tritt ein, wenn die Funktion sich selbst mit einem kleineren oder modifizierten Problem aufruft. Dies führt zu einer schrittweisen Reduktion des Problems, bis der Basisfall erreicht ist.
Ein klassisches Beispiel für Rekursion ist die Berechnung der Fakultät einer Zahl. Die Fakultät von n wird als n! definiert und ist das Produkt aller natürlichen Zahlen von 1 bis n.
Die rekursive Formel lautet: n! = n * (n-1)!.
Der Basisfall ist 0! = 1.
Rekursion kann elegant sein, um bestimmte Probleme zu lösen, kann jedoch auch speicherintensiv und anspruchsvoll zu debuggen sein, wenn sie nicht korrekt implementiert wird. Ein klares Verständnis der Basisfälle und des rekursiven Schritts ist entscheidend, um rekursive Funktionen erfolgreich zu nutzen.
In diesem Beispiel wird die Methode incrementByOne rekursiv aufgerufen, um eine gegebene Zahl um 1 zu erhöhen. Der Basisfall ist, wenn num gleich 0 ist, wobei 1 als das Ergebnis zurückgegeben wird. Im rekursiven Fall wird 1 von num subtrahiert, und dann 1 wird zu dem Ergebnis der rekursiven Funktion addiert. Dadurch wird die Zahl schrittweise um 1 erhöht, bis der Basisfall erreicht ist.
public class Addition {
// Iterativ
static int add(int n) {
int sum = 0;
for (int i = 0; i <= n; i++) {
sum+= i;
}
return sum;
}
// Rekursiv
static int addRec(int n) {
if( n == 1) {
return 1;
}else {
return n + addRec(n-1);
}
}
public static void main(String[] args) {
System.out.println(add(5));
System.out.println(addRec(5));
}
}
In diesem Beispiel wird die Methode add rekursiv aufgerufen, um die Addition von zwei Zahlen durchzuführen. Der Basisfall ist, wenn b gleich 0 ist, wobei a als das Ergebnis der Addition zurückgegeben wird. Im rekursiven Fall wird 1 zu a addiert und 1 von b abgezogen, um schrittweise die Addition durchzuführen, bis der Basisfall erreicht ist.
public class RecursiveAddition {
public static int add(int a, int b) {
if (b == 0) {
return a;
} else {
return add(a + 1, b - 1);
}
}
public static void main(String[] args) {
int num1 = 5;
int num2 = 3;
int sum = add(num1, num2);
System.out.println("Die Summe von " + num1 + " und " + num2 + " ist: " + sum);
}
}
Die Fibonacci-Folge ist eine Zahlenfolge, bei der jedes Element durch die Summe der beiden vorherigen Elemente gebildet wird. Die Folge beginnt normalerweise mit den Zahlen 0 und 1. Die ersten paar Zahlen der Fibonacci-Folge sehen so aus:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Schreiben Sie ein Java-Programm, das die ersten n Fibonacci-Zahlen generiert und ausgibt.
Zusätzliche Herausforderung: