Zum Inhalt springen

Endrekursion

aus Wikipedia, der freien Enzyklopädie

Eine rekursive Funktion f ist endrekursiv ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}; auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist.<ref name="sicp">Harold Abelson, Gerald Jay Sussman, sowie Julie Sussman: <templatestyles src="Webarchiv/styles.css" />{{#if:20060903155101 

      | {{#ifeq: 20060903155101 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20060903155101}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20060903155101}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Linear Recursion and Iteration | {{#invoke:WLink|getEscapedTitle|Linear Recursion and Iteration}} | {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20060903155101|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1}}
    || {{#if:  || }}
  }}{{#if: Linear Recursion and Iteration
    | {{#if: {{#invoke:WLink|isBracketedLink|Linear Recursion and Iteration}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}. In: Structure and Interpretation of Computer Programs. Second edition, The MIT Press 1996, ISBN 0-262-51087-1</ref> Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird.

Automatisches Entfernen von endständigen Funktionsaufrufen

Bei der naiven Abarbeitung einer rekursiven Funktion steigt der Speicherplatzverbrauch linear mit der Rekursionstiefe, da bei jedem Funktionsaufruf Speicherplatz für das Aufzeichnen der aktuellen Continuation des Programmflusses und der Funktionsparameter belegt wird (etwa zum Sichern der Rücksprungadresse und des aktuellen stack frame auf dem Aufrufstack). Außerdem kann während der Abarbeitung der aufgerufenen Funktion weiterer Speicherplatz für das Ablegen von funktionslokalen Variablen belegt werden. Bei einem endständigen Funktionsaufruf werden die im für die aufrufende Funktion belegten Speicherbereich abgelegten Werte aber nur noch für die Parameterübergabe an die endständig aufgerufene Funktion benötigt, so dass dieser Speicherbereich wiederverwendet werden kann. Somit können endrekursive Funktionen automatisch (etwa im Rahmen eines Optimierungsschrittes des Compilers) in iterative Funktionen umgeformt werden, deren Speicherplatzverbrauch bei der Abarbeitung unabhängig von der Rekursionstiefe ist. Bei der Umformung werden die Aufrufe der endständigen Funktion durch entsprechende Sprunganweisungen ersetzt (tail call elimination).

Einige Programmiersprachen wie etwa Scheme verlangen die automatische Umformung von endrekursiven Funktionen in iterative Funktionen als Teil ihrer Sprachdefinition. Andere Programmiersprachen wie etwa C, C++ und C# oder Java verlangen diese Umformung nicht, lassen sie aber für die jeweilige Sprachimplementierung als Optimierung zu. Als Optimierung ist diese Technik häufig in Compilern für funktionale Programmiersprachen zu finden, da bei Verwendung eines funktionalen Programmierstils die rekursive/endrekursive Formulierung für viele Algorithmen besonders häufig ist und darum solchen Formulierungen im Rahmen der Programmoptimierung beim Übersetzen durch einen Compiler besondere Beachtung zukommt.

Das automatische Ersetzen von Funktionsaufrufen durch Sprunganweisungen mit Wiederverwendung des aktuellen stack frame erschwert die Ablaufverfolgung eines Programms bei der Fehleranalyse, da der Aufrufstack beim Unterbrechen eines laufenden Programms an einem Haltepunkt die Aufrufreihenfolge der Funktionen nicht vollständig wiedergibt.

Explizite Endrekursion

Die Programmiersprache Clojure bietet den expliziten Aufruf recur für Endrekursion. Dies hat den Vorteil, dass der Compiler es erkennt, wenn der Aufruf nicht aus der Endposition erfolgt, und den Programmierer darauf hinweist.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://clojuredocs.org/clojure.core/recur%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples}}}}|[{{#invoke:URLutil|getNormalized|1=https://clojuredocs.org/clojure.core/recur}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples}}}}]}}{{#if:| ({{{format}}}{{#if:clojuredocs.org{{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://clojuredocs.org/clojure.core/recur%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://clojuredocs.org/clojure.core/recur}}%7C%7C}}}}{{#if:recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples|{{#if:{{#invoke:WLink|isValidLinktext|1=recur - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples|lines=0}}||}}}}{{#if: clojuredocs.org| In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=clojuredocs.org}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:12431||(?)}}}}}}{{#if: 2017-01-18|;}}}}{{#if: 2017-01-18| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2017-01-18 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2017-01-18|class=Zitationswartung}} }} {{#invoke:DateTime|format|2017-01-18|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:clojuredocs.org{{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2017-01-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://clojuredocs.org/clojure.core/recur
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://clojuredocs.org/clojure.core/recur
      | {{#if:{{#invoke:URLutil|isWebURL|https://clojuredocs.org/clojure.core/recur}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://clojuredocs.org/clojure.core/recur Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://clojuredocs.org/clojure.core/recur
       | {{#if:{{#invoke:URLutil|isWebURL|https://clojuredocs.org/clojure.core/recur}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://clojuredocs.org/clojure.core/recur }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://clojuredocs.org/clojure.core/recur
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://clojuredocs.org/clojure.core/recur
      | {{#if:{{#invoke:URLutil|isWebURL|https://clojuredocs.org/clojure.core/recur}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://clojuredocs.org/clojure.core/recur Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://clojuredocs.org/clojure.core/recur
       | {{#if:{{#invoke:URLutil|isWebURL|https://clojuredocs.org/clojure.core/recur}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://clojuredocs.org/clojure.core/recur }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Anwendbarkeit und Verallgemeinerung

Die Anwendbarkeit der Technik zur Ersetzung von endständigen Funktionsaufrufen durch Sprünge ist nicht auf endrekursive Funktionen beschränkt. Scheme verlangt beispielsweise auch über Funktionsgrenzen hinweg die Ausführung von endständigen Funktionen mit konstantem Speicherplatzverbrauch (proper tail recursion), beispielsweise für zwei Funktionen, die einander endständig aufrufen.<ref name="r5rs">{{#invoke:Vorlage:Literatur|f}}{{#if: 

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = 
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Higher-Order and Symbolic Computation
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:Richard Kelsey, William Clinger, Jonathan Rees et al.|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref><ref name="Clinger1998">William Clinger: <templatestyles src="Webarchiv/styles.css" />{{#if:20151030113036
      | {{#ifeq: 20151030113036 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20151030113036}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20151030113036}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Proper tail recursion and space efficiency | {{#invoke:WLink|getEscapedTitle|Proper tail recursion and space efficiency}} | {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20151030113036|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf}}
    || {{#if:  || }}
  }}{{#if: Proper tail recursion and space efficiency
    | {{#if: {{#invoke:WLink|isBracketedLink|Proper tail recursion and space efficiency}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (PDF; 240 kB), Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, Juni 1998, S. 174–185</ref>

Durch den Übergang zu Continuation-passing style lassen sich prinzipiell Programme so umformen, dass alle Funktionsaufrufe durch endständige Aufrufe ersetzt werden. Dazu müssen jedoch alle aufgerufenen Funktionen so umgeformt werden, dass sie eine Continuation als Parameter übernehmen, die sie dann explizit mit Übergabe des Funktionsergebnisses zur Ausführung des weiteren Programmlaufs endständig aktivieren. Bei der Ausführung eines solchermaßen umgeformten Programms wird dann konstanter Speicherplatz für die Ablage der activation records (etwa auf dem Aufrufstack) benötigt, aber der für die Ablage der Fortsetzungen benötigte Speicherplatz ist nicht beschränkt. Als Folge dieser Umformung ist dann die mögliche Rekursionstiefe einer Routine durch den zur Ablage der Fortsetzungen verfügbaren Speicherplatz beschränkt statt durch die Größe des Aufrufstacks.<ref name="eopl">Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: Essentials of Programming Languages. Second edition, MIT Press 2001, ISBN 0262062178</ref>

Beispiele

Gegeben sei die rekursive Funktion sum, die die Summe der ersten n natürlichen Zahlen berechnet: 

 sum(n)
   if n=0
     return 0
   else
     return n + sum(n-1)

Da nicht der rekursive Funktionsaufruf, sondern die Addition die letzte Aktion bildet, handelt es sich nicht um eine endrekursive Funktion. Die Berechnung von sum(3) würde damit folgende Schritte beinhalten: 

sum(3) = 3 + sum(2)
 sum(2) = 2 + sum(1)
  sum(1) = 1 + sum(0)
   sum(0) = 0
  sum(1) = 1 + 0 = 1
 sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

In diesem Fall ist jedoch eine Umformung in eine endrekursive Darstellung möglich. 

 sum(n)
   return add_sum (0, n)

 add_sum(m, n)
   if n=0
     return m
   else
     return add_sum (m+n, n-1)

Die endrekursive Hilfsfunktion add_sum empfängt zwei Parameter m und n und liefert als Ergebnis die Summe aus m und der Summe der ersten n natürlichen Zahlen. Der Aufruf add_sum (0, n) liefert somit das gewünschte Ergebnis, die Summe der ersten n natürlichen Zahlen. Während des Ablaufs der Endrekursion in add_sum werden die Zwischenergebnisse im m-Parameter akkumuliert. In dieser endrekursiven Formulierung würde die Berechnung von sum(3) etwa folgende Schritte beinhalten: 

sum(3) = add_sum(0, 3)
       = add_sum(3, 2)
       = add_sum(5, 1)
       = add_sum(6, 0)
       = 6

Bei der Umformung wurde implizit das Assoziativgesetz für die Addition natürlicher Zahlen ausgenutzt. Die ursprüngliche Definition von sum(n) berechnete sum(3) als 

3 + (2 + (1 + 0))

Die umgeformte Formulierung berechnet denselben Wert als 

((0 + 3) + 2) + 1

Wie jede primitiv rekursive Funktion lässt sich die Endrekursion mittels Iteration darstellen. 

 sum(n)
    m := 0

    while (n > 0) do
      m   := m + n
      n   := n - 1
    end-while
    return m

Rekursive wie iterative Lösungen stellen meist eine direkte Umsetzung eines Problems dar, welches schrittweise analysiert wurde. Platzersparnis und Lesbarkeit gehen dabei auf Kosten der Ausführungszeit. Vielfach lohnt daher die Suche nach effizienteren Algorithmen. So ist der beste Algorithmus zur Berechnung des Beispielfalles vor allem durch die „Gaußsche Schulgeschichte“ bekannt geworden: 

 sum(n) = (n*(n+1)) / 2

Als Beispiel für Endrekursion mit mehreren beteiligten Funktionen hier zwei Funktionen even und odd zur Feststellung, ob eine gegebene natürliche Zahl gerade oder ungerade ist. 

 even(n)
   if n=0
     return true
   else
     return odd(n-1)

 odd(n)
   if n=0
     return false
   else
     return even(n-1)

Die beiden Funktionen rufen sich gegenseitig endständig auf. Für sich genommen ist keine der beiden Funktionen endrekursiv.

Verallgemeinerung

Allgemein ist eine Funktion f endrekursiv, wenn sie sich auf folgende Weise definieren lässt:

<math> f(x) = \begin{cases} s(x), & \mbox{falls }R(x)\\f(r(x)), & \mbox{sonst} \\ \end{cases} </math>

Dabei sind r und s beliebige nicht mittels f definierte Funktionen und R die Abbruchbedingung.

Siehe auch

Einzelnachweise

<references /> pt:Recursividade (ciência da computação)#Funções recursivas em cauda

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Endrekursion&oldid=12431“