1. 재귀함수(Recursive Function)
Recursive Function
•
자기자신을 부르는 함수이며, 재귀함수도 함수이기 때문에 값을 입력받아 특정 연산을 수행하여 결과를 반환합니다.
•
귀납적 계산 방법을 따릅니다.
•
귀납적 계산법이란, f(x)를 구하기 위해 또 다시 f(x)를 활용하는 형태입니다.
•
귀납적 계산법은 계산하기 위해 자기자신을 사용하는 식과 멈춰야 하는 기저조건이 존재합니다.
2. 수학적 귀납법
수학적 귀납법
•
명제 P(n)이 모든 자연수 n에 대하여 성립함을 보이는 것입니다.
•
증명 순서
1. P(1)이 참임을 보입니다.
2. P(k)가 성립한다고 가정한 후, P(k + 1)이 성립함을 보입니다.
3. 따라서 모든 자연수 n에 대하여 P(n)이 성립한다고 증명할 수 있습니다.
•
재귀함수가 정확한 값을 반환하는지 증명하기 위해 수학적 귀납법을 사용합니다.
3. 재귀함수 디자인 절차
Tip
1.
먼저 문제 속에서 재귀적 패턴(자기자신을 사용하는 패턴)을 파악해야 합니다.
2.
함수의 역할을 말로서 정확하게 정의합니다.
3.
기저조건에서 함수가 제대로 동작함을 보입니다.
4.
함수가 제대로 동작한다고 가정하고 함수를 완성합니다.
func getFactorial(_ N: Int) -> Int {
//N의 Factorial을 구하는 함수, 0! = 1
//Base Condition(기저조건)
if N == 0 {
return 1
}
return N * getFactorial(N - 1)
}
Swift
복사