1. 개요
프로그래밍 공부를 하다보면 리커젼 기법을 반드시 만나게 된다. 그리고 이 부분에서 수 많은 탈락자가 발생한다.
마치 C언어의 배열, 포인터, 그리고 파일 입출력, 자료구조의 뒤를 잇는 허들이다. 나 역시 리커젼을 아직도 완벽히
이해를 못한다. 단순히 기초만을 알 뿐이다. 하지만 이번에 내 스승님이 된 책을 읽으면서 리커젼의 기본적인 틀을
배웠다. 바로 이렇다.
스승님이 말하셨다. 모든 리커젼을 이 틀에서 벗어나질 못한다.
if ( 종료 조건 )
return 종료 값
else if ( 또 다른 종료 조건 )
return 또 다른 종료 값
else
return ( 몇 가지 작업 ) and then ( 재귀 호출 )
정말이지 위대한 틀이다. 이 틀에 가장 적합한 부분은 합, 팩토리얼, 피보나치 수열이다. 이 세 가지 기법은 모두
기업 면접과 시험에 다 만나봤다. 그렇기 때문에 반드시 숙지해야한다. 나한테 하는 말이다. 특히 우리나라에서
가장 큰 게임 기업의 면접 코딩 문제 중 하나로 리커젼을 통한 1부터 n까지의 합을 구하는 문제가 있었고 또 다른
가장 큰 게임 기업의 필기 시험 문제에서는 피보나치 수열을 리커젼으로 풀 때 문제점과 반복문으로 바꾸는 문제
가 있었다. 물론 나는 잘 풀었다. 그래서 합격했다.
1부터 N까지 합을 구하는 코드를 리커젼으로 작성하면 이렇다.
int Function ( int n ){
if ( n == 0 )
return 0;
else
return n+Function(n-1);
}
정확히 위의 표현식과 일치한다.
만약 내가 스승님을 좀 더 빨리 만났다면 그 면접 시간에 이 코드를 작성하지 못해 허둥대고 당황하고 식은 땀을
흘리면서 세상에서 가장 길면서도 짧았던 그 면접 시간을 안느끼고 순식간에 풀어냈겠지.
반드시 위의 표현식을 기억하자 !!
그리고 또 하나 반드시 익혀야 할 것!
모든 리커젼 기법은 반복문으로 작성할 수 있다. 이것도 연습해야 한다. 이를 해낼 수 있을 때 실력이 한층 발전한다.
2. 재귀 vs 반복
(1) 일반적으로 반복 방식이 재귀보다 성능면에서 효율적이다. ( 재귀 방식은 함수 호출의 오버헤드가 크다. )
(2) 그럼에도 재귀를 쓰는 이유는 몇몇 문제에서 명확한 반복 알고리즘이 존재하지 않을 수 있다. 또한
몇몇 문제에서 반복적인 방법들 보다 재귀적인 해결책이 가장 적합할 수 있다.
(3) 재귀 코드는 반복 코드보다 짧고 쉽다. 그러므로 메모리 공간을 써서 가독성을 높이는 결과를 만든다.
(4) 재귀 코드는 자신을 호출할 때마다 원래 문제의 범위보다 조금씩 줄어들어야 한다. (반드시!)
(5) 재귀 코드의 비효율적인 문제를 해결하기 위해서 동적 프로그래밍(Dynamic Programming)이 등장했다.
이는 재귀 코드의 시간을 획기적으로 줄일 수 있다. ex) 2^n을 n^2이나 또는 n^2을 nlogn으로 풀어낸다.
3. 결론
(1) 재귀와 반복이 싸우면 반복이 우세하다. 하지만 나중에 나오는 동적 프로그래밍을 위해서 재귀는 필수다.
(2) 하지만 동적 프로그래밍은 나중에 어마어마하게 사용된다. 기업 코딩 시험에서도 안나오는 경우가 거의 없다.
(3) 즉, 재귀 공부를 미치도록 하자! (어지간한 문제는 재귀로 다 풀린다.)
