Rekursion Informatikklausur?

Ich schreibe in ein paar Tagen über Rekursion.

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

Danke im Voraus

3 Antworten

Erzesel

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren

29.09.2020, 16:56

Ja die lieben Rekursionen...

In Sachen Programmierung sollte man jedoch davon absehen , außer es ist unumgänglich. Rekursive Funktionen rufen sich selbst auf und legen Daten auf dem Stack ab. Bei heutigen Speichergrößen an sich kein Problem, wenn der Stack dynamisch verwaltet wird.

Dies können jedoch nicht alle Programmiersprachen. Einige haben ein Recursionslimit ,wie: (Python .. ein definierbares..), (JavaScript ..Browserabhängig zwischen 9000 und 32000 Recursionen), (Powershell ...100 ,Batch .. setlocal 32 level, purer call/Selbstaufruf ...abhängig von der Environmentgröße und Systemspeicher ... keine Auslagerung möglich... 100 bis 1000)

Eine "beliebte" und gefürchtete Variante ist die Forkbombe . Entfesselte Rekursion in Reinform und zum Selbstzweck.

Forkbomb.cmd

%0|%0

Auch unter Win 10 mit 16 GB Speicher? Diese vielleicht nicht, aber es geht aggressiver und exponentiell...

Ohne eindeutig erreichbare Abbruchkriterien sind Rekursionen immer kritisch .

Wenn nur irgendmöglich sollte man Iteration verwenden

http://www.phasinma.de/Java/page8/page8.html

https://www.inf-schule.de/algorithmen/algorithmen/rekursion/rekursioniteration/exkurs_rekursioniterativ

regex9

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren, Java, Informatik

29.09.2020, 13:42

An sich alles, was mit Wiederholung einer Aufgabe / Iteration zutun hat.

Klassische Aufgaben, die mir gerade einfallen:

Wort rückwärts ausgeben
Traversion durch einen Baum (pre-/post-/in-order)
Berechnung von Zahlen in der Fibonacci-Folge
Berechnung von Zahlen im Pascal'schen Dreieck
Berechnung der Fakultät
Binäre Suche
Türme von Hanoi
Palindrom erkennen
Primzahl erkennen

jort93

29.09.2020, 13:15

Du kannst alles rekursiv umsetzen. Zumindest alles was überhaupt auch iterativ funktioniert.

Viel sinn ergibt die frage also nicht.

Das Problem von Hanoi, mit den Türmen, kann man ja rekursiv lösen, wie lange hat es gedauert, bsi jemand den Ansatz gefunden hat? Was glaubt ihr?

...zur Frage

Labyrinth Rekursiv kürzesten Pfad finden?

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.

...zur Frage

Rekursion Informatik=> unverständliches Beispiel?

Hey,

Ich verstehe diesen Sachverhalt nicht. Warum ist n=4 und warum rechnen wir 2* rekursiv()?

Also warum die 2*?

Und wie kommt man bei 2*rekursiv(3) auf 2*2*2*2?

Ich verstehe das ganze Schaubild unten nicht.

Über Antworten würde ich mich sehr freuen!

...zur Frage

Labyrinth Rekursiv durchsuchen Performance?

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();
}

...zur Frage

Java: Rekursion mit Array zwischenspeichern?

Betrachten Sie die rekursiv definierte Funktion Q.

Zur Berechnung von Q(n) für höhere n sollten Sie bereits berechnete Resultate in einem Array speichern, z.B. als statisches Attribut in ihrer Klasse. Ansonsten wird der naive Ansatz nicht terminieren.

Hat jemand einen Vorschlag, wie das mit dem Speichern des Zwischenergebnis in einem Array gehen soll?

Ich habe da mal einen Ansatz mit einer Hilfsmethode, aber irgendwie komme ich nicht ganz drauf.

Vielen Dank im Voraus.

Smokie

...zur Frage

Tipps für Klausur in Programmierung ( Java)?

Es gibt bestimmt Personen mit Erfahrung von euch und ich habe Zeitmängel und überlege wie ich am besten vorgehen sollte.Die Vorlesungen sind Katastrophe.Ich weiß ,aber die meisten Themen die in die Klausur vorkommen.Also die Themen : Arrays,Listen,Rekursion und Generics und Theorie.Habt ihr Tipps wo man solche Themen am besten lernen könnte?Was hält ihr von lernen auf Englisch?Das was mir Sorgen macht ist ,dass wenn ich die Themen auf englisch lerne,es kann ja sein ,dass ich dann die Aufgaben (in Text Format auf Deutsch) nicht vestehe.

...zur Frage

For schleife für die ersten hundert durch 3 teilbaren Zahlen?

Ich schreibe morgen eine Informatikklausur und verstehe hier die Aufgabe 5 b nicht so richtig.

Kann mir einer erklären wie das funktioniert?

...zur Frage

Rekursion - Wofür und womit?

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!

...zur Frage

Wie funktioniert Rekursion(Python)?

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.

...zur Frage

Java Rekursion mit Potenzzahlen?

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?

...zur Frage

Java: Wie kann ich Array-Werte rekursiv verschieben?

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]);
  }
}

...zur Frage

Wie stellt man die Gaußsche Summenformel rekursiv in c++ dar?

Hallo, eine Funktion soll die Summe zwischen 1 und einer vom Nutzer eingegebenen Zahl a rekursiv berechnen... also soll die Funktion ja mehrmals aufgerufen werden. Ich habe versucht die Gaußsche Summenformel so einzubringen.. wo ist mein Fehler?

    int rekursion(int a) {
               return (a*(rekursion(a+1))/2)

...zur Frage

Java: Rekursion mit String-Methoden?

Hallo,

wir haben momentan das Thema Rekursion und dazu habe ich eine Frage.

private String wasTueIch(String wort) {
  if (wort.length() <= 1)
    return wort;
  else
    return wasTueIch(wort.substring(1, wort.length())) + wort.charAt(0);
}

Meine Frage ist, warum die Methode rekursiv ist und wie man einen Palindromtester (Palindrom: ein Wort, welches gespiegelt die gleiche Bedeutung hat) einbauen kann.

...zur Frage

Frage zu Java Rekursion (Dezimalzahl in das übergebene Zahlensystem umwandeln)?

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.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen