Laden...

Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen? [iteratives Türme von Hanoi]

Erstellt von hauptmann vor 18 Jahren Letzter Beitrag vor 17 Jahren 21.037 Views
H
hauptmann Themenstarter:in
704 Beiträge seit 2003
vor 18 Jahren
Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen? [iteratives Türme von Hanoi]

Hi!

Eine einfache Frage an die theoretischen Informatiker hier: Gibt es eine rekursive Definition die sich nicht iterativ darstellen lässt?

[last.fm](http://www.last.fm/user/hauptmanAlpha/)
S
8.746 Beiträge seit 2005
vor 18 Jahren

Bei der linearen Rekursionen würde ich ich sagen, nein, gibt es nicht. Bei nicht-linearer Rekursion bin ich mir nicht so sicher. Aus dem Bauch heraus würde ich sagen: Ja, weil sich Schleifen nur in fester Ordnung schachteln lassen.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo hauptmann,

Rekursion und Iteration sind gleichwertig. Es gibt nichts, was nur auf eine Art geht.

herbivore

S
8.746 Beiträge seit 2005
vor 18 Jahren

Gibt es doch bestimmt einen Beweis für!?

Was in jedem Falle gilt, ist dass eine Iteration sich immer in eine Rekursion überführen läßt.

Beim zweiten Nachdenken würde ich sagen, dass man immer einen iterativen Interpreter schreiben kann, der Stacks und damit rekursive Aufrufe nachbildet. Also hat man die Abbildung.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo svenson,

ja, gibt es. Irgendwas mit Turingmächtigkeit. Ich hoffe du erwartetst nicht, dass ich den im Kopf habe. 🙂

herbivore

M
456 Beiträge seit 2004
vor 18 Jahren

Ja, mit Turing könnte man es beweisen.
Nicht primitiv rekursive Funktionen sind Turingvollständing und While-Berechenbare Funktionen sind ebenfalls Turingvollständig. Die Beweise dafür findet man eigentlich in jedem Buch zur theoretischen Informatik.
Somit kann ich jede rekursiv berechenbare Funktion iterativ formulieren und umgekehrt, weil beide die gleiche Menge von berechenbaren Funktionen abdecken.

I am Jack's smirking revenge.
I am Jack's raging bile duct.
I am Jack's cold sweat.
I am Jack's complete lack of surprise.
I am Jack's broken heart.
I am Jack's wasted life.

Q
992 Beiträge seit 2005
vor 18 Jahren

Ist denn wirklich der Unterschied groß?

Bei Rekursion wird ein Job auf den Stack gepackt und abgearbeitet.
Genauso kann ich bei der Iteration selber eine Liste pflegen, und die Jobs abarbeiten.

Oder bin ich da auf dem Holzweg?

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo Quallo,

Rekursion und Iteration sind erstmal grundsätzlich unterschiedliche Konzepte.

herbivore

Q
992 Beiträge seit 2005
vor 18 Jahren

Ach, tatsächlich? g
Das ist mir schon klar, ich weiß was das ist, ich habe hier im Board auch schon diverse Beispiele dazu gepostet, auch Performance-Messungen.

Da rekursive Funktionen intensiv mit dem Stack arbeiten, muss man nur den Stack nachbilden in einer Iterativen Schleife, schon hat man aus Rekursion eine Iteration gemacht.

Die Abarbeitung des Stacks ist doch nicht anderes als Iteration.
Nimm den obersten Job und führe ihn aus...
Nimm den obersten Job und führe ihn aus...
Nimm den obersten Job und führe ihn aus...

Das geht solange, bis kein Job mehr da ist(ich weiß schon, dass es sich um Funktionsaufrufe bzw. deren Daten auf dem Stack handelt).

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo Quallo,

naja, das Rekursion und Iteration gleichmächtig sind, wurde ja schon gesagt. 🙂

In der Regel wird man aber anders umsetzten, als du geschrieben hast. Weil das ja dann jeweils quasi nur Pseudo-Iteration oder Pseudo-Rekursion ist.

herbivore

Q
992 Beiträge seit 2005
vor 18 Jahren

Das ist mir schon klar, dass das Pseudo ist.
Allerdings ist es ein einfaches Beispiel, wie man Rekursiven Code in Iterativen umwandelt.

Der richtige Beweis würde mich mal interessieren.
Ne URL wäre schön.

Grüße, Christoph

D
462 Beiträge seit 2005
vor 18 Jahren

Interessant wäre z.B. das 8-Damen-Problem iterativ zu lösen.

Ich hätte da ehrlich gesagt nicht so nen Plan, wie ich anfangen sollte ...

M
456 Beiträge seit 2004
vor 18 Jahren

I am Jack's smirking revenge.
I am Jack's raging bile duct.
I am Jack's cold sweat.
I am Jack's complete lack of surprise.
I am Jack's broken heart.
I am Jack's wasted life.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo DeveloperX,

ich habe mal Türme von Hanoi iterativ gelöst. Schon lustig. Habe den Code leider nicht mehr.

herbivore

_
416 Beiträge seit 2005
vor 18 Jahren

Hallo

Eine einfache Frage an die theoretischen Informatiker hier: Gibt es eine rekursive Definition die sich nicht iterativ darstellen lässt?

Eigentlich ist die Frage ziemlich praktisch. Deshalb wird das auch gleich im ersten Stufiensemester im Teilgebiet "Praktische Informatik" behandelt.

Jetzt nich ganz korrekt, aber auschaulich.
Eine Funktion welche in jedem Ausführungszweig maximal einen rekursiven Aufruf enthält kann iterativ formuliert werden. D.h. auch ohne Stack.

Bspw:

f(x) {
    if(x=0) return;
    if(x>5) f(x-5) else f(x+4);
}

kann einfach in

f(x){
    while(x!=0) {
        if (x>5) x-=5; else x-=4;
    }
}

umformuliert werden, da egal was passiert höchstens ein f aufgerufen werden kann.

ich habe mal Türme von Hanoi iterativ gelöst. Schon lustig. Habe den Code leider nicht mehr.

Und sicher hast du einen Stack benutzt. Und nichts anderes macht ein Rechner wenn er eine rekursive Funktion aufruft.

@maxE:
da haust du jetzt verschiedene gleich klingende Begriffe durcheinander. Rekursiv im Sinne von Turingberechenbar, heißt einfach nur berechenbar. D.h. eine konstante Funktion ist genauso rekursiv, wie eine Addition usw.
Aber deshalb würde niemand auf die Idee kommen eine solche Funktion rekursiv zu implementieren.

cu, tb

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo tb,

Und sicher hast du einen Stack benutzt. Und nichts anderes macht ein Rechner wenn er eine rekursive Funktion aufruft.

nein, natürlich nicht.

herbivore

M
456 Beiträge seit 2004
vor 18 Jahren

@maxE:
da haust du jetzt verschiedene gleich klingende Begriffe durcheinander. Rekursiv im Sinne von Turingberechenbar, heißt einfach nur berechenbar. D.h. eine konstante Funktion ist genauso rekursiv, wie eine Addition usw.
Aber deshalb würde niemand auf die Idee kommen eine solche Funktion rekursiv zu implementieren.

Wieso durcheinander hauen? Nicht primitiv rekursive Funktionen (hier hab ich die partiell rekursiven Funktionen gemeint, wenn das undeutlich war) sind mit jeder Turingmaschine darstellbar, also Turingvollständig. Natürlich kann man die Addition rekursiv darstellen. Die Addition ist eine primitiv rekursive Funktion. Du kannst sie also mit einem While-Programm und sogar einem Loop-Programm darstellen. Allerdings ist nicht jedes While-Programm mit primitiver Rekursion darstellbar.

I am Jack's smirking revenge.
I am Jack's raging bile duct.
I am Jack's cold sweat.
I am Jack's complete lack of surprise.
I am Jack's broken heart.
I am Jack's wasted life.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo zusammen,

hier Türme von Hanoi einmal rekursiv und einmal iterativ. Ich hoffe das mir keiner mein Array als Stack auslegt. Ich habe die iterative Funktionen extra nicht dokumentiert, damit sie noch mystischer wirkt. Ich meine, dass ich das damals noch kürzer hatte, aber auf die Schnelle ist es jetzt erstmal so wie es ist.


using System;

abstract class App
{
   public static void Main (string [] astrArg)
   {
      MoveTowerR (10, 1, 3);
      Console.WriteLine ("---");
      MoveTowerI (10, 1, 3);
   }

   public static void MoveTowerR (int iHeight, int iFrom, int iTo)
   {
      if (iHeight <= 0) {
         return;
      }
      int iTmp = 6 - iFrom - iTo;
      MoveTowerR (iHeight - 1, iFrom, iTmp);
      Console.WriteLine ("Nr. {0} von {1} nach {2}", iHeight, iFrom, iTo);
      MoveTowerR (iHeight - 1, iTmp, iTo);
   }

   public static void MoveTowerI (int iHeight, int iFrom, int iTo)
   {
      int [] aiFrom = new int [iHeight];

      int iDisk;
      int iLastDisk = 0;
      int iTmp;

      for (iDisk = 0; iDisk < iHeight; ++iDisk) {
         aiFrom [iDisk] = iFrom;
      }

      int iMoves = 2;
      for (int i = 1; i < iHeight; ++i) {
         iMoves *= 2;
      }
      --iMoves;

      for (int iMove = 1; iMove <= iMoves; ++iMove) {
         for (iTmp = iMove, iDisk = 1, iTmp = iMove; iTmp % 2 == 0; ++iDisk, iTmp /= 2) {
         }
         if (iMove == 1) {
            if (iHeight % 2 == 0) {
               iTmp = 6 - iFrom - iTo;
            } else {
               iTmp = iTo;
            }
         } else {
            if (iMove % 2 == 1) {
               if (iMove % 4 == 1) {
                  if (iLastDisk % 2 == 1) {
                     iTmp = 6 - aiFrom [0] - aiFrom [iLastDisk-1];
                  } else {
                     iTmp = aiFrom [iLastDisk-1];
                  }
               } else {
                  iTmp = aiFrom [1];
               }
            } else {
               iTmp = 6 - aiFrom [iDisk-1] - aiFrom [0];
            }
         }

         Console.WriteLine ("Nr. {0} von {1} nach {2}", iDisk, aiFrom [iDisk-1], iTmp);
         aiFrom [iDisk-1] = iTmp;
         iLastDisk = iDisk;
      }
   }
}

herbivore

P
939 Beiträge seit 2003
vor 18 Jahren

Ich hoffe das mir keiner mein Array als Stack auslegt.

Ein Stack, kein Zweifel.

Denn in der iMove-Schleife wird das Array am Ende mit

aiFrom [iDisk-1] = iTmp;

verändert. Ohne diese Zeile wäre es ok, denn du würdest ohne zusätzliche Zwischenspeicherstruktur - Stack, Array, was auch immer - auskommen.

Aber das Turm-von-Hanoi Problem ist wirklich ohne "rekursiven" Zwischenspeicher zu lösen. Laut Buneman und Levy (und Wikipedia) muss in jedem Schleifendurchlauf nur bekannt sein, wie gross die Scheiben auf den Türmen sind. Man braucht also immer nur die aktuellen Werte.

Ausführen bis der gesamte Turm verschoben wurde:1.1. Die kleinste verschiebbare Scheibe auf den Stapel rechts von ihr legen
(bzw. auf den ersten, wenn die Scheibe auf dem letzten Stapel liegt).

1.2. Die zweitkleinste verschiebbare Scheibe auf den einzig möglichen Stapel verschieben.

Gruss
Pulpapex

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo Pulpapex,

du hast merkwürdige Vorstellungen von einem Stack, tztztz. In dem Array werden lediglich die Positionen aller Scheiben gemerkt. Sowas bräuchte man schon, wenn man in OnPaint den aktuellen Zustand zeichnen wollen würde. Außerdem sind die Zugriffe nicht stackartig. Kein Push und Pop in Sicht.

Dass man sich Zustände für die weitere Berechnung merkt, heißt nicht automatisch, dass man das in einem Stack tut. Wenn man das Traversieren eines Baums iterativ lösen würde, würde man z.B. vermutlich eine Queue statt einem Stack verwenden. Nach deiner Logik wäre das dann auch ein Stack.

Dann würde mich noch interessieren, wie deiner Meinung nach in dem "Wiki-Algorithmus" ermittelt wird, wo die jeweils kleinste und zweitkleinste verschiebbare Scheibe liegt, wenn nicht dadurch, dass man sich merkt, welche Scheibe wo liegt.

herbivore

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo zusammen,

so, nun hat mir das keine Ruhe gelassen. Hier kommt das ohne Zweifel vollständig iterative Türme von Hanoi. Es wird keine Information über frühere Zustände gespeichert. Alle Informationen werden - ausgehend von den Eingabedaten (iHeight, iFrom, iTo) nur aus der jeweiligen Zugnummer berechnet.

Das ändert aber nichts daran, dass ich schon die vorige Version für vollständig iterativ halte.

Sicher beantwortet diese Version auch meine Frage, wie man die Position der Scheiben bestimmen kann, ohne sie sich zu merken. Trotzdem bleibt die Frage, ob das in dem Wiki-Algorithmus so gemeint ist, oder ob man sich den Zustand nicht doch einfach merken würde.


public static void MoveTowerI (int iHeight, int iFrom, int iTo)
{
   int iMoves = NumMoves (iHeight);
   for (int iMove = 1; iMove <= iMoves; ++iMove) {
      int iDisk = DiskToMove (iMove);
      Console.WriteLine ("Nr. {0} von {1} nach {2}",
                         iDisk,
                         PosAfterMove (iDisk, iMove-1, iHeight, iFrom, iTo),
                         PosAfterMove (iDisk, iMove,   iHeight, iFrom, iTo));
   }
}

public static int NumMoves (int iHeight)
{
   int iMoves = 2;
   for (int i = 1; i < iHeight; ++i) {
      iMoves *= 2;
   }
   return --iMoves;
}

public static int DiskToMove (int iMove)
{
   int iDisk;
   int iTmp;
   for (iDisk = 1, iTmp = iMove; iTmp % 2 == 0; ++iDisk, iTmp /= 2) {
   }
   return iDisk;
}

public static int PosAfterMove (int iDisk, int iMove, int iHeight, int iFrom, int iTo)
{
   int iMoves = NumMoves (iHeight);
   int iHalf = iMoves / 2 + 1;
   int iPos = 0;
   for (int i = 0; i < iHeight - iDisk + 1; ++i) {
      if (iMove < iHalf) {
         iPos = iFrom;
         iTo = 6 - iFrom - iTo;
      } else {
         iPos = iTo;
         iFrom = 6 - iFrom - iTo;
      }
      if (iHalf == 0) {
         break;
      }
      iMove %= iHalf;
      iHalf /= 2;
   }
   return iPos;
}

Tja, auch mit sowas kann man sein Zeit verbringen. 🙂

herbivore

PS: Hier zum Vergleich noch mal die rekursive Variante aus meinem Beitrag weiter oben. Im Vergleich zeigt sich, dass ein iteratives Vorgehen bei Problemen, bei denen sich Rekursion anbietet/aufdrängt, zwar möglich, aber kompliziert und praktisch gesehen unsinnig ist:

public static void MoveTowerR (int iHeight, int iFrom, int iTo)
{
   if (iHeight <= 0) {
      return;
   }
   int iTmp = 6 - iFrom - iTo;
   MoveTowerR (iHeight - 1, iFrom, iTmp);
   Console.WriteLine ("Nr. {0} von {1} nach {2}", iHeight, iFrom, iTo);
   MoveTowerR (iHeight - 1, iTmp, iTo);
}
4.506 Beiträge seit 2004
vor 18 Jahren

Hallo zusammen,

bei mir ist das inzwischen auch schon wieder ne Weile her, aber mir drängt sich jetzt die Frage auf, was genau macht das bei der Programmierung für einen Unterschied?

Gut, hier wird des öfteren erwähnt, dass beim itarativen Vorgehen kein Stack benutzt wird, was dann wohl auf einen geringer benötigten Arbeitsspeicher schließen lässt, aber wo bleibt die Effizienz?

Ich mein jetzt auch nicht die Laufzeiteffizienz, sondern die Zeit, die man benötigt, ein Problem definitiv itarativ anstatt rekursiv zu lösen. Das mag bei den Türmen von Hanoi noch so Step-By-Step zu entwickeln sein, aber bei komplexeren Problemen? Ich würde mir hier niemals die Mühe machen, und zwingend einen itarativen Weg zu entwickeln.

Deshalb bleib ich bei der mir am schnellsten einfallenden Lösung...

Aber das war jetzt nur meine persönliche Meinung, und nichtsdestotrotz gefallen mir solche Ausschweifungen ebenso, leider fehlt mir momentan die Zeit dazu mich intensiv in solche Dinge einzubringen ...

Ciao
Norman-Timo

A: “Wie ist denn das Wetter bei euch?”
B: “Caps Lock.”
A: “Hä?”
B: “Na ja, Shift ohne Ende!”

M
456 Beiträge seit 2004
vor 18 Jahren

Sicher, kommt wie immer auf den Zusammenhang an. Viele Dinge sind rekursiv einfacher zu lösen und andere Dinge macht man besser iterativ.
z.B. ist das Durchsuchen von Baumen rekursiv meist einfacher zu lösen, als einen iterativen Algorithmus dafür zu nehmen.
Anders herum könnte man eine Zählschleife mit einer einfachen primitiv rekursiven Funktion nachbauen. Hier ist der iterative Ansatz aber meist intuitiver.

I am Jack's smirking revenge.
I am Jack's raging bile duct.
I am Jack's cold sweat.
I am Jack's complete lack of surprise.
I am Jack's broken heart.
I am Jack's wasted life.

T
512 Beiträge seit 2006
vor 17 Jahren

Sorry dass ich das nochmal hochhole. Ist herbivores Schuld, der hat auf den Thread verlinkt 😁

Im Grunde stimmt es, dass Rekursion und Iteration gleichmächtig sind. Aber passt auf, wenn ihr das in einer Prüfung sagt. Es gibt nämlich auch Definitionen von Rekursion, die nicht so mächtig sind wie das, was wir hier auf dem Computer haben.
Bzw. geht es in der Theoretischen Informatik nicht um "unsere" Rekursion, sondern um die primitive Rekursion. Die ist nur LOOP-Berechenbar und nicht Turing-berechenbar.

Der Unterschied ist, dass man mit LOOP nur Schleifen mit einer vorher festgelegten Anzahl an Iterationen machen kann. Das heißt ich kann nicht in der Schleife auswerten, ob ich abbreche. Ich muss schon bevor die Schleife betreten wird bestimmen, wie oft sie durchlaufen wird. In manchen Programmiersprachen ist die FOR-Schleife so ausgelegt (nicht in C#, ich glaube in Pascal und in Python).

Das hat jetzt nicht wirklich praktische Relevanz. Aber wie gesagt in der Prüfung könnte man da leicht auf die Nase fallen, wenn man Rekursion und Primitiv-Rekursive Funktionen durcheinander haut.

e.f.q.

Aus Falschem folgt Beliebiges