재귀와 반복 그리고 꼬리 재귀

앞서서 좋은 프로그래밍 습관을 소개했는데

역시 모든 것은 절대적인 것은 없는 듯 하다.

이전에 진짜라고 생각되던 것들이 또 다시 흔들린다.

변수 이름 짓는 일은 중요하다. 

하지만 이 이름을 짓는데 어떻게 어떻게 하면 좋다라는 절대적인 방법은 없다.

관념적으로 추상적으로 다른 이가 봤을 때, 한 눈에 알아볼 수 있으면 된다.

알고리즘을 작성하는 데는 다양한 기법이 존재한다. 하지만 그 중에서도 

재귀 코딩은 가장 간결하며 또한 가장 미감이 풍부한 기법이다.

추상적인 관념을 담기에 작성하는 데에 고민이 필요하지만 일단 작성되면

그 가독성은 누구보다 뛰어나다.

하지만 재귀의 미감은 정말 뛰어나지만 아쉽게도 실행 스택의 오버 헤드 문제가 있다.

왜냐하면 계속 자신 속을 파고들며 실행 스택을 사용하기 때문이다.

그렇기에 함수의 재귀적 호출 횟수가 일정 이상을 넘게 되면 알고리즘의 실행 속도가 저하된다.

그래서 몇몇의 프로그래밍 고수들은 for나 while 루프를 이용하는 방법을 선호하는 경우가 많다.

재귀 알고리즘을 이용할 것인지 for나 while 루프를 이용할 것인지는 전적으로 프로그래머 본인의

취향에 달린 일이지만 분명한 것은 이 두 가지 방법 사이에 존재하는 장단점이 명백하다는 사실이다.

재귀 알고리즘은 산뜻하고 명쾌하지만 (상대적으로) 무겁고 느리며

for나 while 루프를 직접 돌리는 방식은 가볍고 빠르지만 코드가 (상대적으로) 읽기 어렵고 멋이 없다.

(그러니까 둘 다 할 줄 아는게 중요하다. 필요에 맞게 

 

 멋을 살려야 하는 부분에선 재귀로, 성능과 오류 위험을 살려야하는 부분에선 for나 while 루프를 사용하자)

그리고 이러한 두 가지 방법 사이에서 각자의 장점을 취하는 특이한 알고리즘이 존재한다.

그것이 바로 '꼬리 재귀 (tail recursion)'이다. 

원리는 이렇다.

재귀가 느려지는 이유는 일을 끝마치고 돌아갔을 때, 해야 할 일이 남아있기 때문이다.

하지만 꼬리 재귀는 원래 시점으로 돌아갔을 때, 이 해야할 일이 없는 경우이다. 

이렇게 재귀적 함수를 원래 함수의 꼬리 부분에서 호출하는 경우를 일컬어 꼬리 재귀라 부른다. 

모든 재귀 알고리즘이 '꼬리 재귀'의 형태로 작성될 수 있는 것은 아니지만 조금만 생각해 보면

많은 재귀 알고리즘이 '꼬리 재귀' 기법으로 작성될 수 있다.

*컴파일러가 꼬리 재귀를 인식하는 경우에는 함수가 재귀적으로 호출될 때 리턴되는 위치를 스택에 저장하지 않는다.

따라서 이런 컴파일러에서 꼬리 재귀가 사용되면 재귀 알고리즘이 일반적으로 가지는 단점이 없다. (멋있다.)

그럼 과연 

다음의 함수는 일반 재귀 일까? 꼬리 재귀 일까?

int foo ( int n )

{

if ( n == 0 )

{

return 1;

}

return 2 * foo ( n - 1 );

}

답은 꼬리 재귀가 아니다.

왜냐하면 다시 돌아온 위치에서 2를 곱해야 하는 처리 과정이 존재하기 때문이다.

꼬리 재귀는 다음과 같은 형태이다.

int gcd ( int m, int n )

{

if ( n == 0 )

{

return m;

}

else

{

return gcd ( n, m%n );

}

}

더이상 처리 과정이 없는 경우를 일컫는다.

재귀 for 또는 while 루프 그리고 꼬리 재귀 까지 항상 알고리즘 기법을 생각하며 프로그램을 작성하자.