재귀함수와 Stack

재귀함수는 스택자료구조를 내포하고있다!

DFS(3) 
│
├── DFS(2) 
│   │
│   ├── DFS(1) 
│   │   │
│   │   ├── DFS(0) 
│   │   │   │
│   │   └── print("1 ")
│   │
│   └── print("2 ")
│
└── print("3 ")

import Foundation

func DFS(_ x: Int) {
    if x > 0 { return } 
    else {
        DFS(x-1)
        print(x, terminator: " ")
    }
}

// Usage
if let n = Int(readLine() ?? "") {
    DFS(n)
}

• 재귀함수가 실행될 때는 스택자료구조를 이용해서 작동하게된다
• 알고리즘 입장에서 재귀함수는 반복문의 대체제이다
• 위의 예시를 보면 DFS가 스택구조로 쌓여 다음과 같이 로그가 찍힌다

재귀함수를 이용한 이진수 출력

import Foundation

func dfs(_ x: Int) {
    if x == 0 {
        return
    } else {
        dfs(x / 2)
        print(x % 2, terminator: "")
    }
}

if let n = Int(readLine() ?? "") {
    dfs(n)
}

• 재귀함수는 깊이우선탐색이라고 볼 수 있다
• 재귀함수가 실행되고 마지막 탈출조건 만족후 다시 되돌아갈 때, 이를 BackTracking이라고 부른다