재귀 (Recursion)

며칠 전에 순열 공부하면서 재귀도 잠깐 살펴봤었는데
재귀 지옥에 빠져서 한참동안 헤맸던 기억이 있다.

1부터 N까지의 합을 구하는 함수

#include <bits/stdc++.h>
using namespace std; 

int sum(int n){
	if(n == 1) return 1;
	return n + sum(n -1);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n; 
	cin >> n;
	cout << sum(n);
	
  return 0;
} 

1부터 N까지의 합을 구하는 함수 sum을 재귀로 구현해보았다.

올바른 재귀함수

1. 특정 입력에 대해서 자기 자신을 호출하지 않고 종료할 수 있다. (종료 조건이 있어야 한다.)
2. 모든 입력은 종료 조건으로 수렴해야 한다.

재귀함수를 사용할 때 종료 조건이 있어야 한다.
그렇지 않으면 무한루프가 발생한다.

재귀를 사용할 때는 인자로 무엇을 받을지,
어디까지 계산하고 다시 재귀 호출할지 정해주어야 한다.

하나의 함수가 자신을 여러 번 호출하면 비효율적일 수 있다.

피보나치를 재귀로 구현했을 때 살펴보면

int fibo(int n){
	if(n <= 1) return 1;
    return fibo(n-1) + fibo(n-2);
}

fibo(5)인 경우 fibo(4), fibo(3) 호출하고,
fibo(4)가 fibo(3), fibo(2) 호출하고, fibo(3)이 fibo(2), fibo(1)을 호출하고..와 같이
이미 계산한 것을 또 계산하는 경우가 있어서 비효율적이기 때문이다.

재귀함수는 자기 자신을 부를 때 스택에 누적이 된다.

메모리 구조의 스택 영역에 재귀 함수가 호출 될 때마다 누적되어 쌓인다.
알고리즘 문제를 푸는 사이트에서 설정된 스택 메모리가 작다면 재귀 호출로 인해 메모리 제한에 걸릴 수 있다. 이 경우에는 반복문을 사용해서 푸는 방법을 고려해보자.

---

참고 자료
[실전 알고리즘] 0x0B강 - 재귀