Wo braucht man Rekursion, beim Programmieren?

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?

5 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

ohwehohach

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Technik, programmieren, Technologie

20.01.2022, 16:54

Ständig, wenn es darum geht, baumartige Strukturen zu durchlaufen. Oder schnell zu sortieren. Oder einfach immer dann, wenn eine schicke Rekursion viel eleganter ist, als ein ewig langer iterativer Algorithmus.

Muenze3006co

Fragesteller

20.01.2022, 16:55

Kann ich verstehen dass das schicker ist xD Aber es ist sicherlich bei großen Strukturen langsamer als was iteratives, warum benutzt man es dann überhaupt, gerade dann wenn es um Schnelligkeit geht?

ohwehohach

20.01.2022, 16:55

@Muenze3006co

Es ist nicht langsamer - zumindest nicht immer. Zumindest gibt es erstmal keinen Grund, warum das so sein sollte.

Muenze3006co

Fragesteller

20.01.2022, 16:57

@ohwehohach

Echt nicht...? Was ist dann mit meiner Fakultätsfunktion? Im Durschnitt ist sie um 0.00011s (gemessen) langsamer als bei der Iterativen Lösung

ohwehohach

20.01.2022, 16:58

@Muenze3006co

Kommt ja darauf an, wie Du sie programmiert hast. Und 0.00011s kannst Du an einem normalen Windows PC gar nicht messen. So genau löst das gar nicht auf ;-) Mal abgesehen davon, dass 0.00011s vernachlässigbar sind. Je komplexer der Algorithmus iterativ ist, desto mehr geht das Pendel in Richtung Rekursion

Muenze3006co

Fragesteller

20.01.2022, 16:58

@ohwehohach

Ähm doch...xD Mit python... ich habe es mit dem "time" Modul gemacht und es ist sogar noch viel genauer xD

bei meinen Windows 10 PC: 20 Stellen nach dem Komme, so genau

ohwehohach

20.01.2022, 17:02

@Muenze3006co

OK, ich war bei Timer-Auflösung. Da kann Windows nur höchstens 18ms auflösen - zumindest war es immer mal so. Sei's drum.

Nehmen wir an, Du kannst wirklich so genau messen und hast eine repräsentative Messung gemacht (Also beispielsweise 100.000 mal rekursiv vs. 100.000 mal iterativ und das dann gemittelt), ist immernoch der Fak-Algorithmus iterativ so simpel, dass der Aufwand für die rekursiven Aufrufe eventuell höher ist.

Programmiere mal einen Quicksort sowohl rekursiv als auch iterativ und dann miss nochmal.

Muenze3006co

Fragesteller

20.01.2022, 17:03

@ohwehohach

Dacht ich mir schon...

Programmiere mal einen Quicksort sowohl rekursiv als auch iterativ und dann miss nochmal.

Muss ich mal ausprobieren

PeterKremsner

20.01.2022, 17:11

@Muenze3006co

Langsamer oder nicht langsamer ist immer eine Frage dessen wie komplex der Algorithmus wird.

Wenns einfache Algorithmen sind die Iterativ sehr schön dargestellt werden können wie die Berechnung einer Fakultät sind die Iterativen Verfahren viel schneller weil eben der komplette Overhead für den Funktionsaufruf wegfällt.

Zudem sind iterative Algorithmen weniger Speicheraufwändig.

Wenns hingegen darauf hinaus läuft, dass der Iterative Algorithmus extrem komplex wird im Vergleich zum Rekursiven hat der Rekursive die Nase vorn.

Btw Python ist aber mit dem normalen Python Interpreter genau genommen auch schon von sich aus sehr langsam, der gibt dir eben schon alleine deswegen einen größen Overhead für Funktionsaufrufe usw mit als zB C das macht. In C++ besteht zudem die Möglichkeit mittels Template Meta Programming Rekursive Funktionen komplett aufzulösen sofern zur Kompile Time bekannt ist wie oft diese Aufgerufen werden. Da dir dann der Kompiler bereits die Rekursion auflöst hat das auch gar keinen Einfluss auf die Laufzeit mehr.

grtgrt

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Informatik

20.01.2022, 16:55

Wo Algorithmen rekursiver Natur sind, sollten sie unbedingt auch rekursiv notiert werden: Alles andere wäre deutlich umständlicher (und deswegen weniger wertvoller Code).

BeamerBen

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Technik, programmieren

20.01.2022, 17:44

Du brauchst nicht unbedingt Rekursion, es ist manchmal einfach nur der einfachste Lösungsweg.

Das muss man manchmal einfach als Entwickler abschätzen ob es sinnvoll ist oder nicht.

Ich musste mal stark verschachtelte Daten verarbeiten und da war Rekursion eben der offensichtlichste Weg. Hätte ich da mit Schleifen gearbeitet wäre es einfach ein komplexerer und unübersichtlicherer Lösungsweg geworden. Performance war mir in dem Moment gar nicht mal wichtig.

Woher ich das weiß:Berufserfahrung – Software Entwickler / Devops

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Technik, programmieren

20.01.2022, 17:08

Überall dort, wie sie die naheliegende Umsetzung sind und die Performance hinreichend gut ist.

Insbesondere bei Rekursiven Strukturen, bietet sich die Rekursion an, um entsprechende Probleme zu lösen.

Bei Divide an Conquer bietet sich auch oft eine Rekursion an.

tunik123

20.01.2022, 17:00

Ich hatte heute ein Beispiel für einen anderen Fragesteller. Er wollte Stirlingzahlen berechnen.

https://www.gutefrage.net/frage/wie-kann-man-einfach-die-stringzahl-zweiter-art-brechnen-es-gab-mal-so-einen-trickalgorithmus-den-ich-wo-gesehen-habe-finde-das-nicht-merh

https://de.wikipedia.org/wiki/Stirling-Zahl#Eigenschaften_2

Die rekursive Formel ist schön einfach, bei der expliziten Formel würde man sich einen Wolf programmieren.

Hallöchen, ich soll momentan eine Facharbeit schreiben über Passwortsicherheit (falls jetzt jemand sagt dass ich mir doch was anderes aussuchen hätten soll dann sry aber ich hab das thema vorgeschrieben bekommen) und mein Fachlehrer gab mir die Aufgabe einen Password cracker zu programmieren... Ich habe nur leider keine Erfahrungen im Programmieren.

Es soll halt durch Zufallsprinzip ein gewisses Passwort suchen wie bei Brute force angriffen. Dabei soll es aber angeben wie lange es dauert (also Zeit und wie viele programdurchläufe es braucht) um das richtige Password zu bekommen... Daraus soll ich dann eine Statistik erstellen und das Programm erklären...

Kann mir vielleicht jemand dabei helfen oder einen kleinen Tipp geben? Ich bin wirklich total ratlos :( Ich bedanke mich schonmal für jede Hilfe. LG Melina

...zur Frage

Hilfe, wie programmiere ich eine art "bot" der automatisch aufgaben im Webbrowser ausführt?

Mit welchem Programm/Programmiersprache kann ich eine art bot entwickeln der verschiedene programmierte Tasks ausführt? Inspiration dafür ist ein Bot für das spiel "Dark Orbit" der automatisch ein Browserfenster öffnet und dann selbstständigt mit der Maus arbeitet und zu gewissen Zeiten links-klick macht an einer bestimmten stelle auf dem Display :) Wie kann ich meinen eigenen bot programmieren?

...zur Frage

Braucht man zum programmieren Talent?

Hi Leute, ich lerne jetzt seit etwa einem dreiviertel Jahr die Programmiersprache Java. Ich lese Bücher, schaue Videos und programmiere das ganze auf dem PC nach, aber irgendwie habe ich das Gefühl keine richtigen Fortschritte zu machen. Ich frage mich jetzt ob es sein kann das man eine Art Talent braucht um das zu lernen oder ob es einfach nur sehr lange dauert und sehr anstrengend ist. Was meint ihr. Danke schonmal ;D

...zur Frage

Ist es schwer ein Code zu schreiben für das online Spiel slither.io?

Ich kann kein Programmieren, indem Spiel geht es, um einen Wurm, der immer größer werden soll, durch die hellen Punkte

Meine Frage ist es schwer ein extensions oder so zu programmieren, mit dem man z.B. unsichtbar ist für andere oder bei dem es egal ist ob man an jemanden dranstößt, weil man dann nicht stirbt

Kann man sowas programmieren, ist das schwierig, wie lange braucht man dafür?

Wie viel würde das kosten, wenn das jemand für einen macht? Ich frag nur so

...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

Schleifen in Rekursiv umwandeln?

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

...zur Frage

Wie macht man einen selbstständigen Baum ?

...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

Wie lange braucht man um C# zu lernen?

Ich würde gerne C# lernen um irgendwann meine eigenen Spiele zu programmieren.

Habe aber bis dato noch nie einen Kontakt mit einer anderen Programmiersprache gehabt und würde gerne mal wissen wie lange man als blutiger Anfänger brauch um das ganze so gelernt zu haben das man spiele programmieren könnte.

Ps: ich weiß das jeder einzelne anders schnell bzw langsamer lernt und versteht es zu programmieren. Genauso das man nicht auf Anhieb die komplette Sprache lernen muss um überhaupt ein Spiel zu programmieren. Es geht mir hier rein um das Wissen was notwendig wäre um in c# spiele programmieren zu können alles weiter kann man sich danach immer noch nach Bedarf aneignen.

Ich sage schon mal danke für eure Hilfe :)

...zur Frage

Python-Fibonacci Code?

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

...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

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

Binäre Suche: Iterativ vs rekursiv?

Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?

public static int binarySearchIterative(int[] a, int z) {
  int left = 0;
  int right = a.length - 1;

  while (left <= right) {
    int midpoint = (int)((left + right) / 2);

    if (z == a[midpoint]) {
      return midpoint;
    }

    if (z < a[midpoint]) {
      right = midpoint - 1;
    }
    else {
      left = midpoint + 1;
    }
  }

  return -1;
}

public static int binarySearchRecursive(int[] a, int z, int left, int right) {
  int midpoint = (int)((left + right) / 2);

  if (right < left) {
    return -1;
  }

  if (z == a[midpoint]) {
    return midpoint;
  }

  if (z < a[midpoint]) {
    return binarySearchRecursive(a, z, left, midpoint - 1);
  }
  else {
    return binarySearchRecursive(a, z, midpoint + 1, right);
  }
}

...zur Frage

lamda in Python?

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

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen