[Algorithm] Tail Recursion 이란? Optimization 꼬리 재귀 예제 피보나치 수열

 

 

Tail Call

 

Tail Recursion을 이해하기 전에 Tail Call 부터 알아보자. Javascript에서 함수를 호출하면 콜 스택 이라는 영역에 함수 정보를 저장하게 된다. 참조 형식의 메모리 할당 방식을 사용하는 Javascript에서는 함수를 호출하는 순간, 함수에 관한 정보, 함수 내 변수 값들을 저장하는 실행 컨텍스트를 관리한다.

여기서 Tail Call은 상위 함수에서 해야할 일을 만들지 않는 호출 방식이다. 원래 자리로 돌아가 남은 로직을 수행하기 위해 Stack 메모리가 할당 되는데 이 과정에서 메모리 누수가 발생할 수 있기 때문에, Tail Call을 사용해 가장 밑단의 함수에서 모든 일을 다 처리하고 , 상위 함수에는 추가적으로 더 해야 할 로직을 두지 않는 방식이다.

 

Tail Recursion(꼬리 재귀)란?

 

그럼 Tail Recursion은 무엇인가? Tail Call 방식 중에서 Tail Call로 호출하는 함수가 자기 자신인 경우를 의미한다. Tail Recursion을 이해할 때 가장 좋은 예시가 바로 대표적인 재귀 알고리즘인 피보나치 수열을 구하는 문제다. 피보나치 수열은 한개의 함수에서 두개의 재귀 함수가 호출된다.

10번째 피보나치 수열을 구하는 것은 생가보다 쉽다. 하지만 45번째 피보나치 수열을 구하기 위해서 필요한 콜스택 카운터는 3,672,623,805이 필요하다. 100번째는 아예 계산이 안된다.

let count = 0;
const fibo = (n) =>{
  ++count;

  if(n === 0) return 0;
  if(n === 1) return 1;

  return fibo(n-1) + fibo(n-2);
}

 

100번 째 피보나치 수열을 구하기 위해서는 알고리즘 변경이 필수적이다. 꼬리 재귀(Tail Recursion) 알고리즘을 사용하면 콜 스택 수를 줄이면서 수열을 구할 수 있다.

오름차순 정렬 알고리즘 처럼 피보나치 수열에서 매개변수로 전달되는 n-2와 n-1값을 변수에 저장해 둔다. 이로써 콜 스택의 메모리를 할당받아 카운트를 사용할 필요 없이 변수로 처리가 가능하다.

결과값을 보면 놀라울 정도다. 기존 재귀 알고리즘으로 45번째 피보나치 수열을 구하기 위해 36억번 이상의 콜 카운터가 필요했지만, 아래 로직으로는 단 45번 만에 45번째 피보나치 수열을 구할 수 있게 된다.

const fiboTail = (n, pre1, pre2) =>{
  let cur;
  if(n < 2) 
    return n * pre1;

  cur = pre1 + pre2;
  pre2 = pre1;
  pre1 = cur;
  return fiboTail(n-1, pre1, pre2);
}

call fiboTail(5, 1, 0)
 call fiboTail(4, 1, 1)
  call fiboTail(3, 2, 1)
   call fiboTail(2, 3, 2)
    call fiboTail(1, 5, 3)
    return 1 * 5
   return 2 * 3
  return 3 * 2
 return 4 * 1
return 5 * 0

 

Tail Optimization

 

Tail Call을 사용하면 무한히 늘어나는 콜 스택을 통해 낭비되는 메모리를 절약할 수 있다. Tail Optimization은 Tail Call방식을 사용해서 추가적인 스택메모리를 사용하지 않고, 현재 데이터만을 가지고 프로그램을 처리하는 것이다. 상위 로직에서 아무일도 하지 않는 로직을 구성하는 것이다.

프로그래머가 Tail Call을 사용해서 프로그램을 작성한다고 해서 프로그램 개선이 무조건 되는 것도 아니다. 사용자의 웹 브라우저 영역에서 Tail Optimzation을 지원하지 않으면 무용지물이다. 사용자 실행환경에서 지원을 해줘야 프로그래머가 의도한 대로 최대한 적은 스택 메모리를 사용하면서 프로그램 구현이 가능하다.

 

 

[Algorithm] 재귀 알고리즘이란 recursion algorithm