재귀

정의

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

수학적 귀납법

재귀 방식으로 푼다 = 귀납적 방식으로 푼다

1. 1번 도미노가 쓰러진다.
2. k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.

위가 모두 참이면 모든 도미노가 쓰러진다. 라는 결론에 도달할 수 있다.

절차지향적 사고 vs 귀납적 사고

📍 절차지향적 사고

코드가 동작하는 흐름을 그대로 따라간다.

fun1(3) 실행 → 3 출력 → func1(2) 호출 → 2 출력 → func1(1) 호출 → 1 출력 → func1(0) 호출 순으로 진행되고 최종적으로 3 2 1 이 출력된다.

📍 귀납적 사고

1. func1(1)이 1을 출력한다.
2. func1(k)가 k k-1 k-2.....1 순으로 출력하면 func1(k+1)은 k+1 k k-1.....1 을 출력한다.

위의 두 문장이 참이므로 func1(n)는 n부터 1까지 차례로 출력하는 함수이다.

조건

재귀함수는 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하는데 이러한 입력을 base condition이라 한다. 그리고 모든 입력은 base condition으로 수렴해야 한다.

📍 예시

• n이 0일때 자기 자신을 호출하지 않고 종료된다 = base condition
• 이 함수에는 자연수만이 인수로 들어가니 결국 모든 입력은 n = ...3,2,1,0 즉, n이 0일 때로 수렴하게 된다.

💡 TIP

• 재귀에서는 함수를 명확하게 정의해야 한다. 여기서 정의라는 것은 함수의 인자로 어떤 것을 받고 어디까지 계산 후 자기 자신에게 넘겨줄지 명확히 정하는 것이다.
• 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 반복문과 비교했을 때 코드가 간결해진다는 장점이 있지만 함수 호출이 비용이 큰 연산이기 때문에 메모리와 시간적 측면에서 손해를 본다는 단점이 있다. 따라서 상황에 맞게 반복문과 재귀를 사용하는 것이 중요하다.
• 재귀함수의 반환 값이 void : 재귀 함수가 값을 계산하여 반환할 필요 없이, 단순히 출력, 변경 등 어떤 동작만을 수행하는 경우
• 재귀 함수의 반환 값이 void가 아닌 값 : 재귀 함수가 계산한 결과를 리턴해야 하는 경우

⚠️ WARNING

1. 재귀 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.

위의 피보나치 수열을 재귀로 구현하는 경우 base condition은 n이 1 이하일 때이고 모든 입력에 대해 base condition으로 수렴한다. 피보나치 수열의 n번째 항의 값을 구하려면 자기 자신을 여러 번 호출하는 과정에서 이미 계산한 값을 다시 계산해야 하기 때문에 시간 복잡도가 $O(n)$ 보다 훨씬 커진다.

2. 재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 누적되기 때문에 메모리 제한을 넘은 경우 런타임 에러가 발생할 수 있다.