재귀 호출 ( Recursive Call)
함수가 자기 자신을 호출하는 행위를 재귀 호출이라고 합니다.
때문에 탈출 조건이 주어지지 않으면 무한루프에 빠질 수 있습니다.
재귀 호출은 코드를 간결하게 만들 수 있고, 특정 문제를 해결하는 데 효과적일 수 있습니다.
재귀 호출을 사용할 수 있다면 반복문으로도 표현이 가능합니다.
아래와 같은 형식으로 구현합니다.
func recursiveCall() {
guard ... else { return } // 탈출 조건
recursiveCall() // 수행 동작
}
아래는 1부터 number 까지의 숫자를 더하는 재귀 함수입니다.
재귀 호출의 동작 방식은 아래와 같이 표현할 수 있습니다.
자세히 봐야 하니 느린 속도로 제작했습니다.
재귀함수는 메모리 상에서 스택처럼 관리가 됩니다.
print 는 바로 나오지만 return 되는 재귀함수가 스택에 쌓이는 것을 확인할 수 있습니다.
탈출 조건을 만족할 때까지 자기 자신을 호출하고,
조건을 만족한다면 스택에 쌓여진 함수를 실행하면서 결과를 가져오게 됩니다.
다른 그림으로 표현하면 아래와 같습니다.
재귀 호출의 사용 예시는 다음과 같습니다.
팩토리얼
func factorial(_ n: Int) -> Int {
if n == 0 {
return 1
} else {
return n * factorial(n - 1)
}
}피보나치 수열
func fibonacci(_ n: Int) -> Int {
if n == 0 || n == 1 {
return 1
} else {
return fibonacci(n - 1) + fibonacci(n - 2)
}
}이진 탐색
func binarySearch(_ array: [Int], _ target: Int, _ start: Int, _ end: Int) -> Int {
if start > end {
return -1
}
let mid = (start + end) / 2
if array[mid] == target {
return mid
} else if array[mid] > target {
return binarySearch(array, target, start, mid - 1)
} else {
return binarySearch(array, target, mid + 1, end)
}
}하노이의 탑
func hanoiTower(_ n: Int, _ from: String, _ to: String, _ via: String) {
if n == 1 {
print("\(from)에서 \(to)로 이동")
} else {
hanoiTower(n - 1, from, via, to)
print("\(from)에서 \(to)로 이동")
hanoiTower(n - 1, via, to, from)
}
}이진 트리 순회의 구현
class Node {
var value: Int
var left: Node?
var right: Node?
init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) {
self.value = value
self.left = left
self.right = right
}
}
func preOrderTraversal(_ node: Node?) {
if let node = node {
print(node.value)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
}
}
여기까지 봤을 때 궁금점이 생깁니다.
동작 방식에서는 재귀 호출을 한번만 하는 것을 보여드렸는데, 실제 사용에서는 재귀 호출을 여러 번 하기도 합니다.
[프로그래머스] 타겟 넘버 문제를 활용해서 간단한 예시 첨부합니다.
위와 같은 문제에서 numbers : [ 1, 2, 3, 4 ] 이고 target : 4 일 때, return 되는 count 값은 2가 됩니다.
문제에서 DFS 의 동작은 아래와 같이 표현할 수 있습니다.
가장 상단은 함수 호출부 입니다. DFS(-1, 0)
나머지는 DFS( index+1, sum +/- numbers[index+1] ) 에 값을 대입한 것 입니다.
맞는 답을 찾는 과정은 실선, 해답을 찾지 못한 과정은 점선 입니다.
덧셈 연산은 초록색 테두리, 뺄셈 연산은 붉은색 테두리 입니다.
해답의 return 박스는 노란색입니다.
긴 글 읽어주셔서 감사합니다 ^^.
P.S
잘못된 정보는 바로잡아주시면 감사하겠습니다.