Tail Recursion

재귀 함수로, 마지막 구문을 재귀함수로 정의한다. 재귀 호출 후에는 실행할 내용이 남지 않고, 재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환한다. 즉, 과도한 호출로 스택오버플로우(stack overflow)가 발생하여 메모리를 낭비하지 않도록 최적화하는 방법이다.

Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically no
thing is left to execute after the recursion call.

Code

General Fibonacci(C++)

일반적인 피보나치 함수의 계산은 f(n-2) = a와 f(n-1) = b를 더해서 계속 그 다음 수인 f(n) = c를 만들어주는 것이다.

int fib(int n)
{
  int a = 0, b = 1, c, i;
  if (n == 0)
    return;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}

int main()
{
    int n = 10;
	fib(n);
    return 0;
}

Tail Recursion Fibonacci(C++)

Tail Recursion을 적용한 피보나치는, f(n-2) = a와 f(n-1) = b를 더하는 연산을 바로 자기자신을 호출하는데 사용한다. 그리고 base case가 될 때까지 계속 자기 자신을 호출 하다가 최종에서 return을 통해 값을 얻어낸다.

// Tail Recursive Fibonacci
#include <iostream>
using namespace std;
 
int TR_fib(int n, int a = 0, int b = 1)
{
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    return TR_fib(n - 1, b, a + b);
}
 
int main()
{
    int n = 10;
	fib(n);
    return 0;
}

Reference
[1] https://en.wikipedia.org/wiki/Tail_call
[2] https://www.geeksforgeeks.org/tail-recursion-fibonacci/

See Also

• Boundary-value analysis
• Pigeonhole principle
• Rounding error
• Zero-based numbering