Rekursion – die neusten Beiträge

Hallo,

Ich bin erst seit ganz kurzem in dem Thema Pythonprogrammierung wieder drin. Ich habe online eine Coding-Challenge gefunden, bei der man die ersten x Zahlen der Fibonacci-Folge ausgeben soll. Das habe ich dann auch nach kurzem überlegen geschafft und diesen Code hier geschrieben:

a = 0
b = 1

for x in range(10):
    c = a + b
    print(c)
    a = b
    b = c

Allerdings habe ich mir dann mal andere Lösungen im Internet angeschaut, wo die das rekursiv gelöst haben (weiß nicht mal was das ist), oder auf andere sehr komplizierte Wege. Deswegen bin ich halt ziemlich verwirrt. Ist meine Methode zur Lösung des Problems schlecht, oder grade gut, weil sie so simpel ist?

Ich würde mich sehr freuen, wenn mir irgendjemand erklären könnte, ob und wieso meine Lösung schlecht oder gut ist.

Viele Grüße

Code Snake

wie wandle ich jede Schleife in eine rekursive Lösung um? Und wie mache ich das anderes rum?

Mir fällt es aus irgendwelchen Gründen extrem schwer rekusiv zu denken und Programme für die Uni rekursiv zu schreiben. Mit schleifen usw. hab ich schnell eine Idee und auch wenn ich mir dann die rekursiven Musterlösungen anschaue frage ich mich oft, wie ich da nicht drauf kommen könnte. Könnt ihr dieses Problem nachvollziehen und habt ihr Tipps?

Nur das ich es richtig verstanden habe. In dieser Rekursiven funktion rechnen wir quasi immer (n-2)+1 bzw n-1 bis n <= 1 ist?

Oder anders gesagt, dass immer F(1) bzw. n = 1 rauskommt?

Hallo,

ich bin gerade dabei Prolog zu lernen, komme aber bei der Rekursion nicht weiter, ich verstehe einfach nicht wie das genau abläuft, wenn ich z.B.:

zahl(0).

zahl(plusEins(X)) :- zahl(X).

in meiner Datenbasis stehen hab. Warum weiß dann Prolog, dass

zahl(plusEins(plusEins(0))) true ist?

wenn man für X = 0 hat ist ja zahl(0) und somit durch Implikation der Term zahl(plusEins(0)) auch erfüllt. Aber warum soll dann zahl(plusEins(plusEins(0))) auch erfüllt sein?

Es gibt Mengen A und B, wobei A alle lateinischen Kleinbuchstaben und B Zahlen von 0 bis 9 enthält. Es soll eine Rekursion aufgestellt werden, die die Anzahl der Wörter fn der Länge n >= 0 berechnet, wobei keine Ziffern aufeinanderfolgen dürfen. Ich hab irgendwie keine Idee wie ich das machen soll, indem ich auf vorherige Werte zugreife. Weiß jemand weiter?

Hey, also wir hatten als Rekursion : R(k,l) <= R(k-1,l ) + R(k,l-1)

Aber bei R(2,11) <= R(1,11)+R(2,10)

Dann nochmal für R(1,11)<=R(0,11)+R(1,10)

Aber mit R(0,11) kann ich nichts anfangen

Gruß

public static void main(String[] args) {
		System.out.println(potenzRechner(4,3));
	}

	public static int potenzRechner(int potenzzahl1, int potenzzahl2) {
		
		if (potenzzahl2 == 0) {
			return 1;
		} else if (potenzzahl2 == 1) {
			return potenzzahl1;
		} else {
			return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);
		}
	}

Ich habe den Code oben mit einer Rekursiven Methode, der die Potenz der mitgegebenen Zahlen (in dem Fall 4 und 3) errechnet. Jedoch kann ich nicht 100% nachvollziehen was im letzten else Zweig passiert.

(return potenzzahl1 * potenzRechner(potenzzahl1, potenzzahl2 - 1);)

Wird Potenzzahl1 (4) nicht mit sich selbst (4) mal genommen, und das Potenzzahl2 (2) mal? Also 4 * 4 * 4 = 64? Und das solange bis Potenzzahl2 bei 1 ankommt. Also (4^3) 4 * 4 * 4 = 64, (4^2) 4 * 4 = 16, (4^1) 4 = 4. Oder verstehe ich was falsch? Dann sollte doch theoretisch das Ergebnis (64) beim ersten durchlauf schon rauskommen, für was dann eine Aufgabe bei der man das Rekursiv machen soll?

Zusammengefasst: Kann mir jemand auf gut Deutsch diesen Ausdruck, in der die Rekursion sattfindet, erklären?

Hallo,

ich verstehe den folgenden Schritt nicht ganz:

Wie macht man das?

Warum folgt das?

Liebe Grüße

Hallo,

ich möchte so etwas wie einen Password-List-Generator schreiben, komme aber nicht auf die richtige Rekursionsfunktion.

Es soll zum Beispiel aus einem Zeichensatz wie "abcdef" und der information L = 9 Passwörter im vector<string> zurückgegeben werden, bei denen jeder der Buchstaben an jeder Position 0, 1, .., 9 mal vorkommt, wie beim Passwortgenerator "crunch".

Hat mir jemand ein Code-Beispiel parat?

Viele Grüße

Lukas Z

Kann mir jemand einen Tipp zu dieser Aufgabe geben, wir sind mies überfordert :(

Wenn ich eine Fakultätsfunktion mit Rekursion programmiere ist es bei kleinen n ungefähr so schnell wie eine selbst programmierte Iterative Fakultätsfunktion... Nur wenn das n größer also so 400 wird, dann wird es natürlich messbar langsamer als die Iterative Funktion.

Nun meine Frage: wo braucht man realistisch Rekursion in der Programmiertechnik?

LG

Hey,

ich bereite mich gerade auf eine Informatik-Klausur vor und weiß nicht mehr alle Vorteile von der Trennung von Struktur und Inhalt (also z.B. durch Klasse KNOTEN). Leider konnte ich auch im Schulbuch und im Internet nichts Gutes dazu finden. Ich weiß zwar, dass man dadurch eine bessere Übertragung auf andere Projekte ermöglicht, aber mehr nicht.

Wisst ihr noch mehr Vorteile?

LG

Ich bin dabei ein Labyrinth Rekursiv zu durchsuchen. Klappt auch bei kleinen Labyrinthen.

Code ist folgender, sollte eigentlich selbsterklärend sein denk ich. Problem ist nun folgendes. Der Professor hat viele JUnit Tests geschrieben und bei großen Labyrinthen dauert es zu lang (4s) und bricht daher ab. Wie schreibe ich den Code Performanter? Oder hab ich einen Denkfehler im Code?

Sprache natürlich Java

Ich kann nicht ausschließen, dass die Tests nicht dazu da sind zu erkennen wie performant der Code generell ist. Heißt, dass man guckt wie viele Tests er schafft um zu wissen welche Performance klasse man so etwa hat.

Stack<Coordinate> shortestPath;

private void recursivelyDiscoveryMaze(int x, int y, int depth, Stack<Coordinate> currentPath) {
    //this.maze.prettyPrint();
    currentPath.push(new Coordinate(x, y));
    if (dX == x && dY == y) {
        if (shortestPath.size() > currentPath.size() || shortestPath.size() == 0) {
            shortestPath = (Stack<Coordinate>) currentPath.clone();
        }
        currentPath.pop();
        return;
    }

    this.maze.getMazeField()[x][y] = 1; //set visited
    depth++;
    if (isValidStep(x + 1, y)) //if can be visited
        recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
    if (isValidStep(x, y + 1))
        recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
    if (isValidStep(x - 1, y))
        recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
    if (isValidStep(x, y - 1))
        recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
    depth--;
    this.maze.getMazeField()[x][y] = 0; //set unvisited 
    currentPath.pop();
}

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

Wie der Fragetitel schon sagt, muss ich das Horner Schema rekursiv darstellen (in beliebiger Programmiersprache).
Ich hab einige Stunden damit verbracht, aber bin auf keine rekursive Lösung gekommen, die für Polynome mit Grad >= 3 funktioniert.

Anzumerken ist auch, dass nach einer Multiplikation kein rekursiver Abstieg erfolgen darf und aufgrund der Def. des Horner Schema darf auch nicht mit Potenzen gearbeitet werden.

Die Lösung muss rein auf rekursivem Auf-/Abstieg basieren.

Zu meinen Ansätzen:
Je nach dem, wie ich versucht habe das Schema rekursiv darzustellen, wurde entweder das x nicht richtig ausgeklammert, sodass das Anfangspolynom nicht richtig dargestellt wurde, oder die Anordnung der Koeffizienten war falsch, weshalb das Ergebnis dementsprechend falsch wurde.

Ich hoffe, dass mir hier geholfen werden kann!

Danke für eure Mühen vorab

Für die iterative Approximation von π kann eine spezielle Form der Madhava-Leibniz Reihe verwendet werden:

Implementieren Sie Funktionen, die π mit Hilfe der Reihe approximieren und nach n Schritten abbrechen:
a) double piIterative(int n), die pn iterativ mithilfe einer while-Schleife berechnet.
b) double piRecursive(int n), die pn rekursiv berechnet.

Kann mir jemand helfen?

Servus, wir machen in Info gerade Haskell und da werden die Konzepte der Rekursion und Iteration besprochen.

Ich versteh den Unterschied einfach noch nicht. Könnte mir das einer einfach zusammenfassen?

Rekursion und Iteration rufen sich doch beide selber im Funktionsrumpf auf und dekrementieren bis beim conditional statement ein False erscheint. Ich kann den Unterschied einfach nicht sehen.

Danke schonmal für die Antworten :D

Hey, ich habe folgende Aufgabe bekommen:

Und habe bereits die ersten ausgerechnet:

Nur leider stecke ich nun fest. Kann mir jemand einen Ansatz für die richtige geschlossene Form geben?

Hallo, wie kann ich die Rekursionstiefe bestimmen? Oder wie kann ich diese verändern. Bsp.: Die aktuelle Rekursionstiefe beträgt 1 und ich will eine Rekursionstiefe von 2.

Ich möchte die Quersumme einer Zahl berechnen. Die Quersumme soll nicht größer als 9 sein.

Von TinaAusWien bekam ich dieses Snippet:

dsum = lambda n, s=0: dsum(n // 10, s + n % 10) if n else s

print(dsum(123)) # gibt 6 aus

n und s sind die Parameter von lamda. Wie geht es dann weiter, warum dsum und dann die klammern?

Was ich auch noch nicht verstehe ist dieses

if n else s

Was soll diese Anweisung bedeuten?

Hier zu meiner Frage der Quersumme: https://www.gutefrage.net/frage/wie-in-python-die-quersumme-einer-ganzzahl-berechnen

Hier die Antwort von TinaAusWien: https://www.gutefrage.net/frage/wie-in-python-die-quersumme-einer-ganzzahl-berechnen#answer-370123169

Ich schreibe in ein paar Tagen über Rekursion.

Hat jemand konkrete Beispiel was man alle rekursiv in einer Klausur machen kann?

Danke im Voraus

Hallo,

ich habe ein Problem mit einer bestimmten Informatik Aufgabe und finde dazu ebenfalls keine (verständliche) Hilfe im Internet.

Wir haben das Thema Rekursion bzw. die Mathematische Definition dieser und ich steig da nicht wirklich durch...

Würde mich über eine Erklärung oder eine Weiterleitung z.B. zu einem hilfreichem Video freuen.

Danke im voraus
Lg

PS: Im Anhang habe ich die Aufgabe, welche ich nicht verstehe.

Hallo,

ich habe eine Methode geschrieben, die mir true oder false liefert, falls der übergebene String ein Palindrom ist oder nicht. Da ich es rekursiv versuche, habe ich leider Schwierigkeiten.

Kann mir jemand sagen, wo der Fehler liegt? Danke schon mal!

public static void main(String[] args) {
  String s = "aknna";
  int length = s.length();

  System.out.println(isPalindrom(s, length));
}

public static boolean isPalindrom(String s, int length) {
  if (s.length() < 1) {
    return true;
  }

  if (s.charAt(0) != s.charAt((s.length() - 1))) {
    return false;
  }

  return isPalindrom(s, length - 1);
}

public static boolean countDown(int i) {
    if (i < 0) {
        return false;
    }
    if (i == 0) {
        return true;
    }
    countDown(i - 1);
}

Das ist meine Methode: ich bekomme jedoch den Error: Missing return statement. Wie schreibe ich das am besten um, damit ich trotzdem immer noch eine REKURISVE Methode habe, die einfach i-Mal ausgeführt wird wenn i>0 und true zurückgibt oder wenn i < 0 false;

Guten Mittag,

kann mir wer bei folgender Aufgabe helfen? Ich verstehe weder, wie man auf die Zahlenreihe kommt, noch, was der Ausdruck a = max... bedeutet :)

Danke

Hier ist die Aufgabenstellung.

Es ist keine Verdoppelung. Wusste nicht wie ich das sagen soll.

Also ich suche eine rekursive Funktion mit der man b) berechnen kann. Ich steh voll auf dem Schlauch.

a) ist noch einfach. => x/2

weil x/2 in sich selber wieder eingesetzt ist x/4 usw....

aber wie geht das ganze in die andere Richtung??? also bei b)

also dass ich immer in den Schritten 3/4 - 7/8 - 15/16 usw gehe. oder?

siehe Bild.... Daaaaaanke.

Hallo, ich soll zur Übung eine Funktion schreiben, welche das Kartesische Produkt zweier Mengen bildet:

funktion(menge1, menge2)

Ein Bsp: M1 = (1 2 3), M2 = (4 5)

Dann sollte die Funktion folgendes liefern, wobei die Reihenfolge natürlich egal ist: M3 = ((1 4) (1 5) (2 4) (2 5) (3 4) (4 5))

Ich habe leider echt keine Idee wie ich das lösen soll, ohne Schleifen oder extra Variablen zu verwenden. Ich kann ja nicht die Elemente aus den Listen löschen, weil ich sie ja mehrmals benötige.

Hat da jemand einen Ansatz für mich?

Mein Programm gibt mir innerhalb der descending-Methode in

descending(a - 1)

einen Fehler "unreachable statement".

Kann mir da jemand weiterhelfen, wieso das so ist und was ich machen muss damit es läuft?

public class Descending {
  public static void main(String[] args) {
    descending(10);
  }

  public static void descending(int a) {
    if (a == 0) {
      return;

      descending(a - 1);
      System.out.println(a);
    }
  }
}

Danke im Voraus.

Hallo, ich habe seit einer Woche ein paar Aufgaben über die ich in 2 tagen einen Test schreiben muss, ich hab wirklich mein bestes gegeben aber verzweifle hier wirklich. Ich wäre wirklich sehr dankbar wenn sich jemand melden könnte der sich mit der Programmiersprache C (Oder allgemein mit dem programmieren) auskennt und mir hilft. Danke im voraus!

Hey, kann mir jemand helfen? Ich hänge an einer Übung fest und komme nicht weiter.

Die Aufgabe besteht darin, solange von der Konsole Namen einzulesen, bis eine leere Eingabe erfolgt. Dabei sollen bei jeder gültigen Eingabe die vorherigen Eingaben um ein Wert nach rechts verschoben werden.

Beispiel: 00000.

Ich gebe a ein und bekomme a00000. Danach gebe ich b ein, es folgt ba000. Mit einem zusätzlichen c wäre die Ausgabe cba00. Sollte ich bei edcba angekommen sein und gebe den Wert f ein, wird der letzte Wert herausgeschmissen. Das Ergebnis wäre damit fedcb.

Mein bisheriger Ansatz:

public static void main(String[] args) {
  java.util.Scanner scanner = new java.util.Scanner(System.in)
  String [] array = new String [5];
  int i;
  String temp = array[0];

  do {
    array[i] = scanner.nextLine();
  }
  while (scanner.nextLine() != "")

  for (i = 0; i < 5; i++) {
    array[i] = scanner.nextLine;
    array[i] = [i + 1];
  }

  for (i = 0; i < 5; i++) {
    System.out.println(namen[i]);
  }
}

Erste Frage, wie erstelle ich eine iterative Darstellung zu dieser Aufgabe: "Eine Bakterienkultur vergrößert sich alle 3 Stunden um 72,8%. Zu Beobachtungsbeginn hatte sie eine Größe von 1,40 cm². Entwickle eine iterative Darstellung, die das Wachstum der Bakterienkultur beschreibt."

Dann stehen da x0=... und xn+1=... Was soll ich da einsetzen? Und vor Allem, wie komme ich darauf?

Zweite Frage, wie wandle ich iterative Darstellungen wie x0 = 17; xn+1 = 1,1xn in explizite um?

Und andersrum, wie wandle ich explizite Darstellungen wie xn = n12+4 in iterative um? Wäre sehr nett wenn ihr mir helfen könntet. Mfg

Ich versuche gerade zu verstehen, wie Rekursion funktioniert und bin dann auf die Fakultät gestoßen, die man ja rekursiv programmieren kann. Ich verstehe irgendwie nicht, wieso das überhaupt funktioniert, also ich kann dem Programm nicht wirklich folgen. Bei Iteration weiß ich genau was das Programm macht, aber bei Rekursion, weiß ich nicht mal wieso das funktioniert. Ich habe jetzt mal die Fakultätsfunktion programmiert:

def factorial(n):
    if n == 1:
        return 1
    else:
        b = nfactorial(n-1) print(b) return b 

Das Programm gibt mir jetzt durch das "Print" so Zwischenergebnisse und ich kann nicht nachvollziehen, wieso es(z.B. bei Fak(4)) zuerst 12, dann12* 3 und erst zuletzt 1234 berechnet und nicht andersrum. Ich weiß, dass laut Definition Rekursion so funktioniert, also mit Rückeinsetzung, aber am Programm kann ich das nirgendwo erkennen.

LG

Hallo, ich muss für die Uni ein paar Aufgaben programmieren, die meisten habe ich schon, aber nun muss ich das Rucksackproblem rekursiv lösen und habe einen vorgegebenen Methodenkopf:

public static int backtrackingCalculation(List items, int capacity) {}

Im Internet finde ich keine ähnlichen Fälle, da diese immer andere Parameter übergeben dürfen und nun komme ich einfach nicht weiter. Ich sitze schon mehrere Stunden an dieser Methode und habe noch nicht einmal eine Zeile geschafft, da ich keinen Ansatz habe.

Die Liste items, enthält die items die ich benutzen muss. Jedes Item hat einen Wert und ein Gewicht, diese bekomme ich mit getValue und getWeight. Int capacity beschreibt die Menge, die der 'Rucksack' maximal tragen kann. Der Rückgabewert ist vom typ int und soll den Wert (value) enthalten.

Was ich bisher herausgefunden habe ist, dass man jede mögliche Kombination der Items durchgehen muss und immer die bessere Kombination zurückgeben soll, aber ich habe keine ahnung wie ich das machen soll.

Ich muss bis Samstag Abend fertig sein und habe nun schon etliche Internet-Seiten durch, finde aber nichts, was mich weiterbringt.

Vielen Danke schonmal im voraus!!

iterativ hab ich das hinbekommen, (das hat aber mindestens eine laufzeit von O(n^2) ca würd ich jetzt mal schätzen) nur weiß ich jetzt nicht wie ich diese iterative lösung in eine rekusive umwandeln kann. hier mein iterativer umrechner:

public class Roman {

static String toRoman(int n) {
    String [] roman = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
    int [] arab = {1,4,5,9,10,40,50,90,100,400,500,900,1000};
    String Output ="";
    
    for (int i = roman.length-1; i >= 0; i--) {
       int times = n / arab[i]; 
       for (int j = 1; j <= times; j++) {
           Output = Output + roman[i];
       }
      n = n % arab[i]; 
    }
    return Output;
}

public static void main(String[] args) {
    if (args.length==0) return;
    int N = Integer.parseInt(args[0]);
    
    System.out.println(toRoman(N));
}

}

danke schon mal im voraus!

Kann mir bitte jemand den Begriff "Rekursion" erklären? Ich raff das irgendwie nicht... Und bitte keinen Wikipedia link, ich brauch ne erklärung von jemandem, der auch normale wörter nutzt^^

Aaalso kann mir jemand helfen, wie diese Java Programmieraufgabe geht? Habe schon des öfteren mit rekursiven Methoden gearbeitet, jedoch habe ich keinen Ansatz wie ich das hier anstellen soll:

Schreiben Sie eine Methode int gibDarstellung(int zahl, int basis) die ohne Schleifen eine dezimale Zahl in die übergebene Basis umrechnet. Beispiel: (15, 2) wird zu 1111 (also wird quasi 15 in binär zurück gegeben.

Dahinter stand noch in klammern Horner-Schema.

Habe die Aufgabe aus einer Klausurrekonstruktion von einem anderen Studenten, könnte also sein, dass die Aufgabe in "echt" auch ein bisschen anders aussah.

Ich soll in Informatik ein Referat über Rekursion halten und finde nichts über die Anwendungsgebiete. Es geht nur um mathematische Probleme wie das Potenzieren, Fibonacci oder Fakultäten, aber benutzt man die Rekursion wirklich nur da oder auch woanders? Und zweitens: Mit welchen Programmen bzw Anwendungen kann ich Rekursionen ausführen? Danke schon Mal für eine schnelle Antwort!