재귀함수
- 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 문제를 푸는 방법
- 반복무능로 구현되는 알고리즘은 재귀함수로 표현할 수 있다.
작은 문제를 먼저 해결하고 큰 문제를 해결하는게 재귀적 아이디어의 핵심
재귀함수는 반드시 탈출조건(base case)이 있어야 한다.
팩토리얼 예제
- 반복문 예제
func factorial (_ n : Int) -> Int {
var answer = 1
for i in 2...n {
answer = answer * i
}
return answer
}
// 1 * 2 <-- answer에 할당
// 2(기존 answer) * 3 <-- answer에 할당
// 6(기존 answer) * 4 <-- answer에 할당
// ... 이런식으로 반복해서 곱해주는 형식- 재귀 예제
func factorialR (_ n : Int) -> Int {
if n == 1 { return 1 }
return n * factorialR(n - 1)
}
// factorialR(3) 일 경우
// 3 * factorialR(2)
// 2 * factorialR(1)
// 1
// n == 1 이 탈출조건(base case)이기 때문에 1을 리턴하면서 마무리피보나치 예제
- 반복문 예제
func fibonacci(_ n : Int) -> Int {
if n == 1 || n == 0 { return n }
var answer = 0
var (a, b) = (0, 1)
for _ in 2...n {
answer = a + b
a = b
b = answer
}
return answer
}- 재귀함수 예제
func fibonacciR(_ n : Int) -> Int {
if n == 1 || n == 0 { return n }
return fibonacciR(n - 1) + fibonacciR(n - 2)
}최대공약수 예제
유클리드 호제법
a를 b로 나눈 나머지를 r이라고 할때 (단, a > b) a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 성질을 이용하는 방법
- 재귀함수 예제
func gcdR(a:Int, b:Int) -> Int {
if a == b { return a }
else if a > b { //
if a % b == 0 { return b }
else { return gcdR(a: b, b: a % b) }
} else {
if b % a == 0{ return a }
else { return gcdR(a: a, b: b % a) }
}
}
gcdR(a: 12, b: 16)