- Recursion 알고리즘
: 모든 리커젼은 아래 틀을 이용한다.
: 아래 틀을 이용해서 리커젼 문제들을 연습하자.
if ( 종료 조건 )
return 종료 값
else if ( 또 다른 종료 조건 )
return 또 다른 종료 값
else
return ( 몇 가지 작업 ) and then ( 재귀 호출 )
: 모든 리커젼 기법은 반복문으로 작성할 수 있다.
- 재귀 vs 반복
(1) 일반적으로 반복 방식이 재귀보다 성능면에서 효율적이다. ( 재귀 방식은 함수 호출의 오버헤드가 크다. )
(2) 그럼에도 재귀를 쓰는 이유는 몇몇 문제에서 명확한 반복 알고리즘이 존재하지 않을 수 있다. 또한
몇몇 문제에서 반복적인 방법들 보다 재귀적인 해결책이 가장 적합할 수 있다.
(3) 재귀 코드는 반복 코드보다 짧고 쉽다. 그러므로 메모리 공간을 써서 가독성을 높이는 결과를 만든다.
(4) 재귀 코드는 자신을 호출할 때마다 원래 문제의 범위보다 조금씩 줄어들어야 한다. (반드시!)
(5) 재귀 코드의 비효율적인 문제를 해결하기 위해서 동적 프로그래밍(Dynamic Programming)이 등장했다.
이는 재귀 코드의 시간을 획기적으로 줄일 수 있다. ex) 2^n을 n^2이나 또는 n^2을 nlogn으로 풀어낸다.
- 결론
(1) 재귀와 반복이 싸우면 반복이 우세하다. 하지만 나중에 나오는 동적 프로그래밍을 위해서 재귀는 필수다.
(2) 하지만 동적 프로그래밍은 나중에 어마어마하게 사용된다. 기업 코딩 시험에서도 안나오는 경우가 거의 없다.
(3) 즉, 재귀 공부를 미치도록 하자! (어지간한 문제는 재귀로 다 풀린다.)
출처: https://makefortune2.tistory.com/5 [Simple in Complex with Simple]
