Um zu verstehen, dass Rekursion tatsächlich gar nicht an Funktionen gebunden ist, ist eher ein theoretischer Rahmen erforderlich, der eher an Ausdruckskraft gebunden ist.
Ich werde nicht in das graben, lassen Google Lücken füllen.
Ja, wir können Funktionen ohne einen Stapel haben.
Wir brauchen nicht einmal die Aufruf/ret Maschinen für Funktionen, können wir nur den Compiler inline jeden Funktionsaufruf haben. So gibt es keinen Bedarf für einen Stapel.
Dies berücksichtigt nur Funktionen im Sinne der Programmierung, nicht mathematischen Sinn.
Ein besserer Name wäre Routinen. Wie auch immer, das ist ein einfacher Beweis für Konzepte, die als wiederverwendbarer Code dienen und keinen Stack benötigen.
Aber nicht alle Funktionen, im mathematischen Sinne, können auf diese Weise implementiert werden.
Das ist analog zu sagen: "Wir können Hunde auf dem Bett haben, aber nicht alle Hunde können auf dem Bett sein".
Sie sind auf dem richtigen Weg mit Rekursion, aber wenn es um Rekursion geht, müssen wir viel formeller sein, da es verschiedene Formen von recursion gibt.
Zum Beispiel kann jeder Funktionsaufruf den Compiler loopen, wenn die inlined Funktion irgendwie nicht eingeschränkt ist. Ohne in die Theorie zu graben, um immer sicher zu sein, dass unser Compiler keine Schleife hat, können wir nur primitive (bounded) recursion zulassen.
Was Sie wahrscheinlich mit "Rekursion" meint ist general recursion, das kann nicht durch In-Lining erreicht werden, können wir zeigen, dass wir eine unendliche Menge an Speicher für GR benötigen, und das ist die Abgrenzung zwischen PR und GR, keine a Stapel.
So können wir Funktion ohne einen Stapel, auch rekursiv (für irgendeine Form von Rekursion) Funktionen.
Wenn Ihre Frage praktischer war, dann betrachten Sie einfach MIPS. In der MIPS-ISA gibt es keine Stack-Anweisungen oder Stack-Pointer-Register, alles was mit dem Stack zu tun hat, ist nur eine Konvention.
Der Compiler könnte einen beliebigen Speicherbereich verwenden und ihn wie einen Stapel behandeln.
Sie könnten immer den Compiler "manuell" einen Bereich des Speichers als eine Stapel-ähnliche Datenstruktur verwenden. Sie können push/pop und call/ret auf x86 emulieren, indem Sie ein anderes Register als RSP verwenden und nur MOV laden/speichern, HINZUFÜGEN und indirekt JMP verwenden. –
Ich erinnere mich auch daran, eine SO-Antwort über Sprachen gelesen zu haben, die Funktion call/ret implementieren, indem sie Zeiger übergeben, anstatt eine Rückadresse zu drücken. Oder etwas, an das ich mich wirklich nicht erinnere. Es war nicht nur ein Link-Register-Äquivalent zum Zurückschieben einer Absenderadresse, es war etwas anderes. Aber ich kann mich nicht genug erinnern, um es wieder zu finden oder etwas Nützliches zu sagen. –