재귀

재귀 ! 예전에 학원에서 일하면서 수업 때문에 백트래킹을 공부하며 어느정도는 감을 잡아두었기 때문에 오늘 학습은 어렵지 않았다.

그래도 한번 더 개념 정리할 수 있는 좋은 시간이었다.

어떤 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법을 재귀(recursion)라고 한다. 재귀를 사용한 코드는 대부분의 경우 더욱 간결하고 이해하기 쉽다.

문제를 쪼개어 생각하는 방법

1. 기존의 문제에서 출발하여 더 작은 경우를 생각한다.
2. 같은 방식으로, 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각한다.
3. 문제가 간단해져서 바로 풀 수 있게 되는 순간부터 앞서 생성한 문제를 차근차근 해결한다.

재귀를 사용하면 좋은 상황

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀 함수는 반복문으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제 해결하기
4. 복잡한 문제 해결하기
5. 코드 구현하기