Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen? [iteratives Türme von Hanoi]
hauptmann
myCSharp.de - Member



Dabei seit:
Beiträge: 704
Herkunft: Österreich/Kärnten

Themenstarter:

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

beantworten | zitieren | melden

Hi!

Eine einfache Frage an die theoretischen Informatiker hier: Gibt es eine rekursive Definition die sich nicht iterativ darstellen lässt?
private Nachricht | Beiträge des Benutzers
svenson
myCSharp.de - Member



Dabei seit:
Beiträge: 8.746
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo hauptmann,

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

herbivore
private Nachricht | Beiträge des Benutzers
svenson
myCSharp.de - Member



Dabei seit:
Beiträge: 8.746
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo svenson,

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

herbivore
private Nachricht | Beiträge des Benutzers
maxE
myCSharp.de - Member



Dabei seit:
Beiträge: 456
Herkunft: Sachsen

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 992
Herkunft: Nähe Bremen

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Quallo,

Rekursion und Iteration sind erstmal grundsätzlich unterschiedliche Konzepte.

herbivore
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 992
Herkunft: Nähe Bremen

beantworten | zitieren | melden

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).
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Quallo
myCSharp.de - Member



Dabei seit:
Beiträge: 992
Herkunft: Nähe Bremen

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
DeveloperX
myCSharp.de - Member



Dabei seit:
Beiträge: 462
Herkunft: .at/ooe&stmk

beantworten | zitieren | melden

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 ...
private Nachricht | Beiträge des Benutzers
maxE
myCSharp.de - Member



Dabei seit:
Beiträge: 456
Herkunft: Sachsen

beantworten | zitieren | melden

Beweis:
http://www.ipd.uni-karlsruhe.de/~christof/da-mc.pdf (ab Seite 23)
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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo DeveloperX,

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

herbivore
private Nachricht | Beiträge des Benutzers
_tb_
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Hallo
Zitat von hauptmann
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.

Zitat von herbivore
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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo _tb_,
Zitat
Und sicher hast du einen Stack benutzt. Und nichts anderes macht ein Rechner wenn er eine rekursive Funktion aufruft.
nein, natürlich nicht.

herbivore
private Nachricht | Beiträge des Benutzers
maxE
myCSharp.de - Member



Dabei seit:
Beiträge: 456
Herkunft: Sachsen

beantworten | zitieren | melden

Zitat von _tb_
@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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Pulpapex
myCSharp.de - Member



Dabei seit:
Beiträge: 939
Herkunft: Rostock

beantworten | zitieren | melden

Zitat von herbivore
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.
Zitat von Wikipedia

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

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

Gruss
Pulpapex
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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);
}
private Nachricht | Beiträge des Benutzers
norman_timo
myCSharp.de - Member

Avatar #avatar-1775.jpeg


Dabei seit:
Beiträge: 4.506
Herkunft: Wald-Michelbach (Odw)

beantworten | zitieren | melden

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!”
private Nachricht | Beiträge des Benutzers
maxE
myCSharp.de - Member



Dabei seit:
Beiträge: 456
Herkunft: Sachsen

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Traumzauberbaum
myCSharp.de - Member



Dabei seit:
Beiträge: 512

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers