재귀(Recursion)란 하나의 함수에서 자기 자신을 다시 호출해서 작업을 수행하는 알고리즘이다. 우리는 일반적으로 문제를 풀 때 A 다음엔 B를 하고, B 다음에는 C를 하고... 와 같은 절차지향적 사고를 하는 경향이 있다.
하지만 재귀함수를 잘 다루기 위해서는 이러한 절차지향적 사고의 틀에서 벗어나 귀납적 사고를 가져야 한다.
귀납적 사고?
귀납적 사고란 k=1일때 성립하고, k=n일때 성립한다고 가정했을 때, k=n+1도 성립한다면 이 함수는 참이라고 생각하는 사고이다.
즉, 이 함수는 정답을 구해줄 것이라고 믿고 프로그램을 작성해야한다. 그렇지 않고 절차적으로 생각하면 생각이 점점 꼬여버린다....
재귀함수 작성법
그렇다면 귀납적 사고를 이용해 재귀함수를 작성하는 방법에 대해 알아보자.
재귀함수에는 2가지의 핵심 요소가 반드시 필요하다.
1. Base condition(종료 조건): 재귀가 멈추는 가장 작은 단위, 더 이상 쪼갤 수 없는 상태
2. Recursive Step(재귀 식): 큰 문제를 작은 문제로 쪼개는 방식, 모든 입력은 Base condition으로 수렴해야 한다.
예를 들어 임의의 숫자 1부터 N까지를 출력하는 코드를 작성해보자.
void func(int n){
if(n==0) return; // Base Condition
func(n-1); // Recursive Step, n==0으로 수렴한다.
cout<<n<<' ';
}n==0일때 프로그램을 종료하여 무한 반복을 방지하고,
func(n-1)을 호출하여 큰 문제를 점점 작은 문제로 쪼개면서 n==0으로 수렴하고 있다.
만약 n이 5라면 func(5) -> func(4) -> func(3) -> .... -> 1출력 -> 2출력 -> ... 와 같이 절차지향적으로 생각할 수 있지만, 만약 n이 매우 큰 숫자라면 절차지향적 사고는 지양해야한다.
재귀함수의 특징
재귀함수에 대한 몇 가지 특징에 대해 알아보자.
- 함수의 인자로 어떤 것을 받고, 어디까지 계산한 후 어떤 것을 자기 자신에게 넘겨줄 지 명확히 정의해야 한다. (return type, void, ...)
- 모든 재귀 함수는 반복문만으로 같은 동작을 하는 함수를 만들 수 있다.
- 재귀 함수는 반복문에 비해 코드는 간결하지만, 메모리/시간에서는 손해를 본다.
- 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적이다.
-> 이는 추후에 Dynamic Programming으로 해결할 수 있다. - 재귀함수가 자기 자신을 호출할 때마다 스택 영역에 계속 누적된다.
-> 만약 Base condition을 잘못 설정해서 무한 루프를 돈다면, 힙 영역과 스택 영역이 충돌하면서 Stack Overflow가 발생할 것이다!
