재귀 함수(recursion)와 반복문(iteration) 장단점과 꼬리 재귀(tail call recursion)의 개념

1. 재귀 함수와 반복문의 장단점 비교

함수를 생성할 때, 반복해서 동작시켜야되는 소스코드를 만들어야 할 때가 있습니다. 이 때, 사용하는 방법이 주로 재귀 함수(recursion)와 반복문(iteration)입니다. 재귀함수와 반복문을 사용할때의 장단점은 아래와 같습니다. 자세한 내용은 아래에서 언급하겠습니다.

2. 반복문

반복문은 동일한 변수를 지속적으로 사용하기 때문에, 새로 함수를 호출할 필요가 없습니다. 재귀함수와 다르게 context switching 비용이 발생하지 않기 때문에, 속도가 빠릅니다.

하지만 for 문을 사용하면 여러 변수를 선언해야 하며, 재귀에 비하여 대부분의 코드는 훨씬 더 긴 경우가 많습니다.

3. 재귀 함수

def n_sum(n, ans):
  if n == 1:
    return 1
  return yes_tail(n-1, ans + n)

재귀 함수는 동일한 함수를 지속적으로 호출하게 됩니다. 재귀 함수를 사용하면 변수를 여러개 만들 필요가 없고, 코드가 간결해진다는 장점이 있습니다.

하지만, 재귀함수를 사용하면 지속적으로 함수를 호출하게 되는데, 이 때 사용하는 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치등을 지속적으로 프로세스의 Stack에 저장해야 합니다. 이는 선언한 변수의 값만 변경해서 사용하는 반복문과 달리 많은 메모리 사용을 의미합니다.

또, 함수 호출과 복귀를 하기 위한 context switching 비용이 발생하기 때문에, 속도가 상대적으로 느립니다. 즉, 오버헤드가 발생하여 속도가 느리게 됩니다.

3.1. 재귀 함수의 단점 해결 방법

재귀 함수의 방법을 해결하기 위해서는 꼬리 재귀 (tail call recursion)라는 기법이 있습니다. 이러한 방법은 컴파일러가 꼬리 재귀 코드를 보고, 적절한 반복문으로 컴파일을 해주어야 동작하는 방법입니다.

꼬리 재귀는 return 문에 연산이 없는 경우에만 적용됩니다. return 문에 함수만 작성되어 있으면 꼬리 재귀지만, 함수만 있는 경우가 아니면 꼬리 재귀로 컴파일 할 수 없습니다.

def yes_tail(n, ans):
  if n == 1:
    return 1
  return yes_tail(n-1, ans + n)

def no_tail(n):
  if n == 1:
    return 1
  return n + no_tail(n-1)

위와 같은 경우 동일한 동작을 하지만 yes_tail 함수처럼 return 에 함수 호출 이외에 다른 연산자가 붙지 않는 경우에는 꼬리 재귀로 컴파일을 효율적으로 할 수 있습니다.