꼬리 재귀 재귀 호출이 함수에 의해 실행되는 마지막 명령문인 재귀 함수로 정의됩니다. 따라서 기본적으로 재귀 호출 후에는 실행할 것이 아무것도 남지 않습니다.
예를 들어 다음 C++ 함수 print()는 꼬리 재귀적입니다.
씨
// An example of tail recursive function> void> print(>int> n)> {> >if> (n <0)> >return>;> >printf>(>'%d '>, n);> >// The last executed statement is recursive call> >print(n - 1);> }> |
>
>
C++
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >cout <<>' '> << n;> > >// The last executed statement is recursive call> >print(n - 1);> }> // This code is contributed by Aman Kumar> |
>
>
자바
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <>0>)> >return>;> >System.out.print(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n ->1>);> }> // This code is contributed by divyeh072019> |
>
>
파이썬3
# An example of tail recursive function> def> prints(n):> >if> (n <>0>):> >return> >print>(>str>(n), end>=>' '>)> ># The last executed statement is recursive call> >prints(n>->1>)> ># This code is contributed by Pratham76> ># improved by ashish2021> |
>
>
씨#
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >Console.Write(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by divyeshrabadiya07> |
>
>
자바스크립트
> // An example of tail recursive function> function> print(n)> {> >if> (n <0)> >return>;> > >document.write(>' '> + n);> > >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by Rajput-Ji> > |
>
>
시간 복잡도: 에)
보조 공간: 에)
꼬리 재귀의 필요성:
꼬리 재귀 함수는 꼬리 재귀가 컴파일러에 의해 최적화될 수 있으므로 꼬리가 아닌 재귀 함수보다 더 나은 것으로 간주됩니다.
컴파일러는 일반적으로 다음을 사용하여 재귀 프로시저를 실행합니다. 스택 . 이 스택은 각 재귀 호출에 대한 매개변수 값을 포함한 모든 관련 정보로 구성됩니다. 프로시저가 호출되면 해당 정보는 다음과 같습니다. 밀린 스택에 저장하고 함수가 종료되면 정보는 다음과 같습니다. 터진 스택에서. 따라서 꼬리가 없는 재귀 함수의 경우 스택 깊이 (컴파일 중 언제든지 사용되는 최대 스택 공간)이 더 많습니다.
꼬리 재귀 함수를 최적화하기 위해 컴파일러에서 사용하는 아이디어는 간단합니다. 재귀 호출이 마지막 명령문이기 때문에 현재 함수에서 더 이상 할 일이 없으므로 현재 함수의 스택 프레임을 저장하는 것은 쓸모가 없습니다(자세한 내용은 여기를 참조하세요). 세부).
꼬리 재귀가 아닌 함수를 꼬리 재귀로 작성하여 최적화할 수 있나요?
n의 계승을 계산하려면 다음 함수를 고려하십시오.
비꼬리 재귀 함수입니다. 언뜻 보면 꼬리 재귀처럼 보이지만. 자세히 살펴보면 Fact(n-1)이 반환한 값이 다음과 같이 사용되는 것을 알 수 있습니다. 사실(n) . 그래서 호출은 사실(n-1) 마지막으로 한 일이 아니야 사실(n) .
C++
#include> using> namespace> std;> // A NON-tail-recursive function. The function is not tail> // recursive because the value returned by fact(n-1) is used> // in fact(n) and call to fact(n-1) is not the last thing> // done by fact(n)> unsigned>int> fact(unsigned>int> n)> {> >if> (n <= 0)> >return> 1;> >return> n * fact(n - 1);> }> // Driver program to test above function> int> main()> {> >cout << fact(5);> >return> 0;> }> |
>
>
자바
class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n ==>0>)> >return> 1>;> >return> n * fact(n ->1>);> >}> >// Driver program> >public> static> void> main(String[] args)> >{> >System.out.println(fact(>5>));> >}> }> // This code is contributed by Smitha.> |
>
>
파이썬3
# A NON-tail-recursive function.> # The function is not tail> # recursive because the value> # returned by fact(n-1) is used> # in fact(n) and call to fact(n-1)> # is not the last thing done by> # fact(n)> def> fact(n):> >if> (n>=>=> 0>):> >return> 1> >return> n>*> fact(n>->1>)> # Driver program to test> # above function> if> __name__>=>=> '__main__'>:> >print>(fact(>5>))> # This code is contributed by Smitha.> |
>
>
씨#
using> System;> class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n == 0)> >return> 1;> >return> n * fact(n - 1);> >}> >// Driver program to test> >// above function> >public> static> void> Main() { Console.Write(fact(5)); }> }> // This code is contributed by Smitha> |
>
>
PHP
// A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used in // fact(n) and call to fact(n-1) is // not the last thing done by fact(n) function fact( $n) { if ($n == 0) return 1; return $n * fact($n - 1); } // Driver Code echo fact(5); // This code is contributed by Ajit ?>> |
>
>
자바스크립트
> // A NON-tail-recursive function.> // The function is not tail> // recursive because the value> // returned by fact(n-1) is used> // in fact(n) and call to fact(n-1)> // is not the last thing done by> // fact(n)> function> fact(n)> {> >if> (n == 0)> >return> 1;> > >return> n * fact(n - 1);> }> // Driver code> document.write(fact(5));> // This code is contributed by divyeshrabadiya07> > |
>
>산출
120>
시간 복잡도: 에)
보조 공간: 에)
위 함수는 꼬리 재귀 함수로 작성할 수 있습니다. 아이디어는 인수를 하나 더 사용하고 두 번째 인수에 계승 값을 누적하는 것입니다. n이 0에 도달하면 누적된 값을 반환합니다.
다음은 tail-recursive 함수를 사용한 구현입니다.
C++
#include> using> namespace> std;> // A tail recursive function to calculate factorial> unsigned factTR(unsigned>int> n, unsigned>int> a)> {> >if> (n <= 1)> >return> a;> >return> factTR(n - 1, n * a);> }> // A wrapper over factTR> unsigned>int> fact(unsigned>int> n) {>return> factTR(n, 1); }> // Driver program to test above function> int> main()> {> >cout << fact(5);> >return> 0;> }> |
>
>
자바
// Java Code for Tail Recursion> class> GFG {> >// A tail recursive function> >// to calculate factorial> >static> int> factTR(>int> n,>int> a)> >{> >if> (n <=>0>)> >return> a;> >return> factTR(n ->1>, n * a);> >}> >// A wrapper over factTR> >static> int> fact(>int> n) {>return> factTR(n,>1>); }> >// Driver code> >static> public> void> main(String[] args)> >{> >System.out.println(fact(>5>));> >}> }> // This code is contributed by Smitha.> |
>
프레디 머큐리
>
파이썬3
# A tail recursive function> # to calculate factorial> def> fact(n, a>=>1>):> >if> (n <>=> 1>):> >return> a> >return> fact(n>-> 1>, n>*> a)> # Driver program to test> # above function> print>(fact(>5>))> # This code is contributed> # by Smitha> # improved by Ujwal, ashish2021> |
>
>
씨#
// C# Code for Tail Recursion> using> System;> class> GFG {> >// A tail recursive function> >// to calculate factorial> >static> int> factTR(>int> n,>int> a)> >{> >if> (n <= 0)> >return> a;> >return> factTR(n - 1, n * a);> >}> >// A wrapper over factTR> >static> int> fact(>int> n) {>return> factTR(n, 1); }> >// Driver code> >static> public> void> Main()> >{> >Console.WriteLine(fact(5));> >}> }> // This code is contributed by Ajit.> |
>
>
PHP
// A tail recursive function // to calculate factorial function factTR($n, $a) { if ($n <= 0) return $a; return factTR($n - 1, $n * $a); } // A wrapper over factTR function fact($n) { return factTR($n, 1); } // Driver program to test // above function echo fact(5); // This code is contributed // by Smitha ?>> |
>
>
자바스크립트
> // Javascript Code for Tail Recursion> // A tail recursive function> // to calculate factorial> function> factTR(n, a)> {> >if> (n <= 0)> >return> a;> > >return> factTR(n - 1, n * a);> }> > // A wrapper over factTR> function> fact(n)> {> >return> factTR(n, 1);> }> // Driver code> document.write(fact(5));> // This code is contributed by rameshtravel07> > > |
>
>산출
120>
시간 복잡도: 에)
보조 공간: 오(1)
이 주제에 대한 다음 기사:
- 테일콜 제거
- QuickSort Tail Call Optimization(최악의 경우 공간을 Log n으로 줄이기)