Tail call (original) (raw)
Eine rekursive Funktion f ist endrekursiv (englisch tail recursive; auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist. Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird.
| Property | Value |
|---|---|
| dbo:abstract | Koncová rekurze, respektive koncové volání, je v informatice taková situace, kdy posledním příkazem funkce je rekurzivní zavolání sebe sama, respektive jiné funkce. Takové volání může šetřit místo na zásobníku volání, pokud to překladač umožňuje. Při předání řízení do podprogramu je totiž možné nahradit obsah rámce současného podprogramu (z něhož už většina informací nebude potřeba) novým obsahem a předat řízení na začátek podprogramu obyčejným skokem, místo aby se musel starý rámec zachovávat a na vrchol zásobníku navíc ukládat rámec nový. Z hlediska běžného procedurálního programování je chytrá úprava koncových volání určitou optimalizací umožňující hlubší „zanoření“ při rekurzi. Naproti tomu ve funkcionálním programování, kde je místo cyklů obvyklé používat rekurzi, je obvykle chytrý překlad koncových volání zaručen standardy daného jazyka (například ve Scheme). Hluboké rekurzivní zanoření je totiž předpokladem fungování programů a tedy není považováno za optimalizaci, ale za nezbytnou součást překladače. (cs) Eine rekursive Funktion f ist endrekursiv (englisch tail recursive; auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist. Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird. (de) En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération. (fr) In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail-end recursion) is particularly useful, and is often easy to optimize in implementations. Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail-call elimination or tail-call optimization. Tail-call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming. In the words of Guy L. Steele, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as [machine code] JUMP instructions." Not all programming languages require tail-call elimination. However, in functional programming languages, tail-call elimination is often guaranteed by the language standard, allowing tail recursion to use a similar amount of memory as an equivalent loop. The special case of tail-recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller. (en) 꼬리 재귀는 재귀 함수를 호출할 때 스택을 재사용하면서 메모리를 과도하게 사용하지 않도록 최적화하는 방법이다. 스칼라 import scala.annotation.tailrec// 예제 1 - 꼬리재귀 팩토리얼def factorial(x: Int): Int = { @tailrec def factorialHelper(x: Int, accumulator: Int): Int = if (x == 1) accumulator else factorialHelper(x - 1, accumulator * x) factorialHelper(x, 1)}// 예제 2 - 꼬리재귀 피보나치def fibonacci(x: Int): Int = { @tailrec def fibonacciHelper(x: Int, a: Int, b: Int): Int = if(x == 0) a else fibonacciHelper(x - 1, b, a + b) fibonacciHelper(x, 0, 1)} (ko) Een staartrecursie (Engels: tail recursion) is een programmeerconcept in de informatica. Bij een procedure spreekt men over staartrecursie indien de recursieve oproep de laatste instructie van de procedure is. Bij een normale procedure-aanroep moeten alle lokale variabelen worden opgeslagen zodat de procedure verder kan worden uitgevoerd zodra de aangeroepen procedure eindigt. Als de recursieve aanroep echter de laatste instructie is, is dit niet nodig, omdat de procedure onmiddellijk na het uitvoeren van de aanroep eindigt. Daarom kan een procedure met een staartrecursie eenvoudig worden omgevormd tot een niet-recursieve procedure met een equivalente iteratie. Sommige compilers optimaliseren een geval van staartrecursie door niet voor iedere recursieve oproep een nieuw stackframe te alloceren, maar de oude opnieuw te gebruiken. Dit leidt tot minder vertraging en minder kans op een stack-overflow. (nl) 末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出しという。呼び出しではなく、戻り先を保存しない飛び越し命令（いわゆる「GOTO文」）にコンパイラ最適化できるという特徴がある（）。 (ja) Rekurencja ogonowa (rekurencja prawostronna, ang. tail call) – rodzaj rekurencji, w której ostatnia operacja wykonywana przez funkcję to rekurencyjne wywołanie samej siebie lub zwrócenie końcowego wyniku. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak i automatycznie, co redukuje wielkość stosu oraz zwiększa wydajność. Ta technika iteracyjnego wykonywania obliczeń jest powszechna w programowaniu funkcyjnym promującym używanie rekurencji, która w przeciwnym wypadku zajęłaby cały dostępny stos. (pl) Svansrekursion är inom datavetenskap rekursion där sista operationen i en funktion är ett rekursivt anrop. En sådan rekursion kan lätt omvandlas till en iteration, och kan på så sätt drastiskt minska utrymmet i anropsstacken som behöver användas. Svansrekursion används ofta i funktionella programmeringsspråk, exempelvis Scheme. (sv) Хвостова рекурсія — це випадок рекурсії, коли рекурсивний виклик функції відбувається наприкінці її роботи. Використовується у мовах програмування для оптимізації, через можливість заміни виклику функції на ітерацію, без використання стеку. Ця оптимізація широко використовується у функціональних мовах програмування, а також у таких мовах програмуваннях як C завдяки прапорцям оптимізації для компілятора. (uk) Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции. Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию путём формальной и гарантированно корректной перестройки кода функции. Оптимизация хвостовой рекурсии путём преобразования её в плоскую итерацию реализована во многих оптимизирующих компиляторах. В некоторых функциональных языках программирования спецификация гарантирует обязательную оптимизацию хвостовой рекурсии. (ru) 在计算机学裡，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。 (zh) |
| dbo:wikiPageID | 1110903 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-es:Recursión_(ciencias_de_computación) dbpedia-pt:Recursividade_(ciência_da_computação) |
| dbo:wikiPageLength | 39191 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123549203 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Program_optimization dbr:Prolog dbr:PureScript dbr:Python_(programming_language) dbr:Scala_(programming_language) dbr:Scheme_(programming_language) dbr:Swap_(computer_science) dbr:Big-O_notation dbr:Algorithmic_efficiency dbr:Andrew_Appel dbc:Recursion dbr:Perl dbr:Perl_(programming_language) dbr:Visual_Basic_.NET dbr:David_H._D._Warren dbr:Call_frame dbr:Inline_expansion dbr:Interpreter_(computing) dbr:Programming_language_specification dbc:Programming_language_implementation dbr:Common_Lisp dbr:Compiler dbr:Course-of-values_recursion dbr:Rust_(programming_language) dbr:Node_(computer_science) dbr:Clang dbr:Elixir_(programming_language) dbr:Elm_(programming_language) dbr:GNU_Compiler_Collection dbr:GOTO dbr:Gerald_Jay_Sussman dbr:Go_(programming_language) dbr:Modulo_(jargon) dbr:Cons dbr:Continuation-passing_style dbr:Corecursion dbr:Lisp_(programming_language) dbr:Lua_(programming_language) dbr:ML_(programming_language) dbr:Call_stack dbc:Scheme_(programming_language) dbr:Stack_frame dbr:Structured_programming dbr:Subroutine dbr:Computer_science dbr:Zig_(programming_language) dbr:Functional_programming dbc:Implementation_of_functional_programming_languages dbr:C_(programming_language) dbr:C_Sharp_(programming_language) dbc:Subroutines dbr:WebKit dbr:Garbage_collection_(computer_science) dbr:Leaf_subroutine dbr:Logic_programming dbr:X86_assembly_language dbr:Daniel_P._Friedman dbr:ECMAScript dbr:Erlang_(programming_language) dbr:F_Sharp_(programming_language) dbr:Goto dbr:Iteration dbr:Functional_programming_language dbr:Groovy_(programming_language) dbr:Return_statement dbr:Guido_van_Rossum dbr:Haskell_(programming_language) dbr:Henry_Baker_(computer_scientist) dbr:Higher-order_function dbc:Control_flow dbr:JavaScript dbr:Tcl dbr:Assembly_language dbr:Association_for_Computing_Machinery dbc:Articles_with_example_C_code dbr:Chicken_(Scheme_implementation) dbr:LISP dbc:Articles_with_example_Scheme_(programming_language)_code dbr:High-level_programming_language dbr:Java_virtual_machine dbr:While_loop dbr:Assignment_(computer_science) dbr:Automatic_Reference_Counting dbr:Kotlin_(programming_language) dbr:OCaml dbr:Objective-C dbr:Racket_(programming_language) dbr:Recursion_(computer_science) dbr:X86 dbr:Side_effect_(computer_science) dbr:Safari_(browser) dbr:Loop_(computing) dbr:Evaluation_strategy dbr:Exec_(system_call) dbr:Single_assignment dbr:Parameter_(computer_science) dbr:Lisp_programming_language dbr:Mutually_recursive dbr:Return_address_(computing) dbr:Interpreter_(computer_software) dbr:Trampoline_(computers) dbr:Hardware_stack dbr:Platform_(computing) dbr:Cheney_algorithm dbr:Intel_C_Compiler dbr:Clojure_(programming_language) dbr:Guy_L._Steele dbr:Stack_traces dbr:Jump_(computer_science) dbr:David_S._Wise |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Efn dbt:Notelist dbt:Portal dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Wiktionary |
| dct:subject | dbc:Recursion dbc:Programming_language_implementation dbc:Scheme_(programming_language) dbc:Implementation_of_functional_programming_languages dbc:Subroutines dbc:Control_flow dbc:Articles_with_example_C_code dbc:Articles_with_example_Scheme_(programming_language)_code |
| gold:hypernym | dbr:Call |
| rdf:type | dbo:Work yago:WikicatSubroutines yago:Abstraction100002137 yago:Code106355894 yago:CodingSystem106353757 yago:Cognition100023271 yago:Communication100033020 yago:Concept105835747 yago:Content105809192 yago:Idea105833840 yago:PsychologicalFeature100023100 yago:Writing106359877 yago:WrittenCommunication106349220 yago:Routine106582403 yago:Software106566077 yago:WikicatProgrammingLanguageConcepts |
| rdfs:comment | Eine rekursive Funktion f ist endrekursiv (englisch tail recursive; auch endständig rekursiv, iterativ rekursiv, repetitiv rekursiv), wenn der rekursive Funktionsaufruf die letzte Aktion zur Berechnung von f ist. Vorteil dieser Funktionsdefinition ist, dass kein zusätzlicher Speicherplatz zur Verwaltung der Rekursion benötigt wird. (de) En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération. (fr) 꼬리 재귀는 재귀 함수를 호출할 때 스택을 재사용하면서 메모리를 과도하게 사용하지 않도록 최적화하는 방법이다. 스칼라 import scala.annotation.tailrec// 예제 1 - 꼬리재귀 팩토리얼def factorial(x: Int): Int = { @tailrec def factorialHelper(x: Int, accumulator: Int): Int = if (x == 1) accumulator else factorialHelper(x - 1, accumulator * x) factorialHelper(x, 1)}// 예제 2 - 꼬리재귀 피보나치def fibonacci(x: Int): Int = { @tailrec def fibonacciHelper(x: Int, a: Int, b: Int): Int = if(x == 0) a else fibonacciHelper(x - 1, b, a + b) fibonacciHelper(x, 0, 1)} (ko) 末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出しという。呼び出しではなく、戻り先を保存しない飛び越し命令（いわゆる「GOTO文」）にコンパイラ最適化できるという特徴がある（）。 (ja) Rekurencja ogonowa (rekurencja prawostronna, ang. tail call) – rodzaj rekurencji, w której ostatnia operacja wykonywana przez funkcję to rekurencyjne wywołanie samej siebie lub zwrócenie końcowego wyniku. Taka funkcja może zostać łatwo zamieniona na iterację, zarówno ręcznie, jak i automatycznie, co redukuje wielkość stosu oraz zwiększa wydajność. Ta technika iteracyjnego wykonywania obliczeń jest powszechna w programowaniu funkcyjnym promującym używanie rekurencji, która w przeciwnym wypadku zajęłaby cały dostępny stos. (pl) Svansrekursion är inom datavetenskap rekursion där sista operationen i en funktion är ett rekursivt anrop. En sådan rekursion kan lätt omvandlas till en iteration, och kan på så sätt drastiskt minska utrymmet i anropsstacken som behöver användas. Svansrekursion används ofta i funktionella programmeringsspråk, exempelvis Scheme. (sv) Хвостова рекурсія — це випадок рекурсії, коли рекурсивний виклик функції відбувається наприкінці її роботи. Використовується у мовах програмування для оптимізації, через можливість заміни виклику функції на ітерацію, без використання стеку. Ця оптимізація широко використовується у функціональних мовах програмування, а також у таких мовах програмуваннях як C завдяки прапорцям оптимізації для компілятора. (uk) Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции. Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию путём формальной и гарантированно корректной перестройки кода функции. Оптимизация хвостовой рекурсии путём преобразования её в плоскую итерацию реализована во многих оптимизирующих компиляторах. В некоторых функциональных языках программирования спецификация гарантирует обязательную оптимизацию хвостовой рекурсии. (ru) 在计算机学裡，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。 (zh) Koncová rekurze, respektive koncové volání, je v informatice taková situace, kdy posledním příkazem funkce je rekurzivní zavolání sebe sama, respektive jiné funkce. Takové volání může šetřit místo na zásobníku volání, pokud to překladač umožňuje. Při předání řízení do podprogramu je totiž možné nahradit obsah rámce současného podprogramu (z něhož už většina informací nebude potřeba) novým obsahem a předat řízení na začátek podprogramu obyčejným skokem, místo aby se musel starý rámec zachovávat a na vrchol zásobníku navíc ukládat rámec nový. (cs) In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail-end recursion) is particularly useful, and is often easy to optimize in implementations. (en) Een staartrecursie (Engels: tail recursion) is een programmeerconcept in de informatica. Bij een procedure spreekt men over staartrecursie indien de recursieve oproep de laatste instructie van de procedure is. Bij een normale procedure-aanroep moeten alle lokale variabelen worden opgeslagen zodat de procedure verder kan worden uitgevoerd zodra de aangeroepen procedure eindigt. Als de recursieve aanroep echter de laatste instructie is, is dit niet nodig, omdat de procedure onmiddellijk na het uitvoeren van de aanroep eindigt. Daarom kan een procedure met een staartrecursie eenvoudig worden omgevormd tot een niet-recursieve procedure met een equivalente iteratie. (nl) |
| rdfs:label | Koncová rekurze (cs) Endrekursion (de) Récursion terminale (fr) 꼬리 재귀 (ko) 末尾再帰 (ja) Staartrecursie (nl) Rekurencja ogonowa (pl) Tail call (en) Хвостовая рекурсия (ru) Svansrekursion (sv) Хвостова рекурсія (uk) 尾调用 (zh) |
| owl:sameAs | freebase:Tail call yago-res:Tail call wikidata:Tail call dbpedia-cs:Tail call dbpedia-de:Tail call dbpedia-fi:Tail call dbpedia-fr:Tail call dbpedia-he:Tail call dbpedia-ja:Tail call dbpedia-ko:Tail call http://lt.dbpedia.org/resource/Uodeginė_rekursija dbpedia-nl:Tail call dbpedia-pl:Tail call dbpedia-ru:Tail call dbpedia-sr:Tail call dbpedia-sv:Tail call dbpedia-tr:Tail call dbpedia-uk:Tail call dbpedia-zh:Tail call https://global.dbpedia.org/id/M17B |
| prov:wasDerivedFrom | wikipedia-en:Tail_call?oldid=1123549203&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tail_call |
| is dbo:wikiPageRedirects of | dbr:Tail-end_recursion dbr:Tail_Recursion dbr:Tail_call_elimination dbr:Tail_call_optimization dbr:Tail-call_optimization dbr:Tail_recursion dbr:Proper_tail_recursion dbr:Tail-call_elimination dbr:Tail-call_optimisation dbr:Tail-recursion dbr:Tail-recursion_optimization dbr:Tail-recursive dbr:Tail-recursive_function dbr:Tail_function dbr:Tail_recursion_elimination dbr:Tail_recursion_modulo_cons dbr:Tail_recursion_optimization dbr:Tail_recursive dbr:Tail_recursive_function dbr:Tailcall |
| is dbo:wikiPageWikiLink of | dbr:Prolog dbr:Proportion_extend_sort dbr:Python_(programming_language) dbr:Quicksort dbr:Scala_(programming_language) dbr:Scheme_(programming_language) dbr:Escape_analysis dbr:Clojure dbr:Free_Pascal dbr:Continuation-passing_style dbr:Corecursion dbr:Coroutine dbr:Tail-end_recursion dbr:Tail_Recursion dbr:Tail_call_elimination dbr:Lisp_(programming_language) dbr:ML_(programming_language) dbr:Standard_ML dbr:Funarg_problem dbr:Tail_call_optimization dbr:Mutual_recursion dbr:Prolog_syntax_and_semantics dbr:Quickselect dbr:ECMAScript dbr:Exponentiation_by_squaring dbr:F_Sharp_(programming_language) dbr:Goto dbr:History_of_the_Scheme_programming_language dbr:Microcontroller dbr:Region-based_memory_management dbr:Haxe dbr:IronScheme dbr:AVL_tree dbr:SuperCollider dbr:Tail-call_optimization dbr:Tail_recursion dbr:Stack_trace dbr:Direct_function dbr:C-- dbr:Portable_Standard_Lisp dbr:Source_(programming_language) dbr:Racket_(programming_language) dbr:Recursion_(computer_science) dbr:Segmentation_fault dbr:Racket_features dbr:Perl_control_structures dbr:Perl_language_structure dbr:Proper_tail_recursion dbr:Tail-call_elimination dbr:Tail-call_optimisation dbr:Tail-recursion dbr:Tail-recursion_optimization dbr:Tail-recursive dbr:Tail-recursive_function dbr:Tail_function dbr:Tail_recursion_elimination dbr:Tail_recursion_modulo_cons dbr:Tail_recursion_optimization dbr:Tail_recursive dbr:Tail_recursive_function dbr:Tailcall |
| is foaf:primaryTopic of | wikipedia-en:Tail_call |