C++ 코딩테스트 알고리즘 개념정리 재귀함수 순열 조합

재귀함수 (Recursion) 알고리즘 공부할 때 제일 처음 공부하게되는 재귀함수 첫 이직 테스트 때 재귀함수가 나왔었지 막연하게 생각하면 내가 나를 호출하는 개념이고 좀 더 정의를 하면 정의 단계에서 자신을 재참조하는 함수 재귀함수는 stack 영역에 덩어리로 쌓이게 되며 호출이 많아질수록 stack 영역 공간이 없어지기 때문에 스택 오버플로가 발생할 수도 있다는 것을 알아야 한다. 그래서 반복문으로 될 것 같은 문제는 반복문으로 푸는것도 좋다.

또, 중요한건 반드시 종료조건이 있어야 한다는 것. 종료조건이 없으면 무한루프에 빠지기 때문 재귀함수의 제일 많이나오는 예제로는 팩토리얼, 하노이탑, 피보나치 수 정도이려나 개념정리이기 때문에 팩토리얼만 간단하게 테스트하고 넘어감 :) 팩토리얼은 n!

으로 표시하고 n * n-1 * (n-2) * (n-3) * .. * 2 * 1 이 된다. 결국 n부터 1이될때까지 수를 하나씩 빼가면서 곱해주는 건데 이걸 n -> n-1 -> n-2 만 ...