재귀 알고리즘

재귀적
자기 자신을 사용하여 정의된 알고리즘

1. 종료조건인 basecase(베이스케이스)
2. 작아진 부문제들로 이루어지는 recursion(재귀케이스)

작동 원리

기본 규칙

1. always 베이스케이스(basecase) 가져야 한다.
2. 재귀호출은 always 베이스케이스(basecase)` 방향으로
3. 꼭 필요할 때만 사용 (성능 저하)

작동원리 같은 그림에 만약 sum(1000000)을 적용한다면 호출이 너무 많아 시간이 오래 걸릴 것이다. 꼭 필요한 것인지 생각해보는게 좋을 것이다

나쁜 재귀

잘못 설계된 재귀는 딱 2가지 케이스
1. 베이스케이스(basecase)가 없거나 도달불가능
2. 재귀케이스가 베이스케이스를 향해 작아진 부문제를 대상으로 재귀하지 않을 때(미정지)

잘 설계된 재귀의 예시

아래의 예시에서 살짝 헷갈렸던건
언제 코드의 마지막 줄이 출력되는지였다.
먼저 rPringDigits 호출로 간다음에 재귀가 끝나면 역순으로 출력하게 된다

Q. 그런데 만약에 나는 3 4 0 8 순서가 아니라 8 0 4 3 순서로 출력하고 싶다면 어떻게 할까?
A. 어렵지 않다. rPrintDigits 호출과 write를 바꿔주면 된다