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