거의 모든 알고리즘에 사용되는 재귀

재귀를 쓰면 다양한 문제에서 간결하고 명쾌한 알고리즘을 짜는데 도와준다.

그리고 제목에 나와있듯이 거의 모든 알고리즘에 사용이 된다.

그럼 아주아주 중요한 재귀를 알아보자.

---

재귀는 자기 자신을 호출한다.

자기 자신을 호출한다는 개념은 뭘까 ? 그리고 무엇을 호출한다는 것일까 ?

일단 간단한 예시를 보면서 이해해보자.

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

아래는 위 코드의 동작방식이다.

사진에선 n=4일 때 동작 방식을 나타냈다.
일단 두번째 줄에 if문을 보면 4==0으로 만족하지 않으니까 밑에 줄을 실행하게 된다.
그러면 또 if문을 보면 3==0은 만족하지 않음으로 밑에 줄을 실행... 쭉 가보자
자 드디어 1==0도 만족하지 않아 밑에 줄인 return 1 + func(0)을 실행하게 되고
if문을 만족하게 되었다! if문을 만족했으면 0을 반환해준다. 여기서 중요하다.

1. func(0)은 0을 돌려줌.
2. func(1)은 1 + func(0)이니까 1을 돌려줌
3. func(2)는 2 + 1이니까 3을 돌려줌
4. func(3)은 3 + 2 = 5를 돌려줌
5. func(4)는 4 + 3 = 7을 돌려줌
6. func(5)는 5 + 4 = 9를 돌려줌

최종적으로 9를 돌려준다.
이렇게 함수를 호출하여 조건을 만족하면 자기자신을 호출한 쪽으로 값을 돌려주는 방식을 재귀 라고 한다.

---

재귀를 쓸 때 주의할 점

재귀함수의 구성요소

(반환값형) func(인수) {
	if(베이스케이스) {
    	return 베이스케이스에 대응하는 처리;
    }
    조건에 만족하지 못한다면 다시 호출 처리;
}

이렇게 보니까 뭔가 복잡하다. 하나씩 살펴보자.

베이스케이스란 ? 조건이다.
앞의 코드는 1+ ... + n을 계산하는 함수이기 때문에 n=0인 경우가 베이스 케이스가 된다.

또 주의해야할 점이, 다시 호출을 처리하는 자리에서 많이 발생한다.
만약 앞의 코드처럼 처리값이 return n + func(n-1)이 아닌 return n + func(n+1)이라면 ? func(6)을 호출했다면 func(7), func(8), func(9), ... 늘어나버린다.
베이스케이스가 0이 될 때인데 반대로 0에서 멀어지니가 무한 호출이 발생된다!

정리하자면

• 제일 처음 호출하는 건 함수func(4)이지만, 최초로 값을 돌려주는 건 조건이 만족하는 함수(func(0)임을 잊지말자.
• 베이스케이스를 처리할 때 0을 반환하거나 빠져나가게 짜지 못하면 무한 반복을 해버린다.
• 재귀 호출을 할 때 인수가 베이스 케이스에 점점 가까워지는지 봐야한다.