재귀함수

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

재귀함수란?

자기 자신을 다시 호출하는 함수를 말한다.

즉, 내 함수 안에서 내 함수를 호출하는 형태이다.

func recursiveFunc() {
    print("재귀 함수를 호출합니다.")
    recursiveFunc()
}

recursiveFunc()

위 코드를 실행하면 "재귀 함수를 호출합니다." 라는 문자열이 무한히 출력된다.

재귀 함수를 사용할 때에는 재귀 함수가 언제 끝날지 종료 조건을 꼭 명시해 주어야 한다. 

※ 종료 조건을 명시해주지 않는다면 함수가 무한히 호출되므로 주의!

 

func recursiveFunc(i: Int) {
    if i == 100 {
        return
    }
    print("\(i) 번째 재귀 함수에서, \(i + 1) 번째 재귀 함수를 호출합니다.")
    recursiveFunc(i: i + 1)
    print("\(i) 번째 재귀 함수를 종료합니다.")   
}

recursiveFunc(i: 1)

//위 코드는 재귀 함수를 100번 호출하도록 작성한 코드이다.

컴퓨터의 구조 측면에서 보면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적제되므로 재귀 함수는 스택 자료구조와 같다.

즉, 재귀 함수는 내부적으로 스택 자료구조와 동일하며, 스택 자료구조를 사용해야 하는 알고리즘은 재귀 함수를 사용하여 간편하게 구현할 수 있다. 대표적으로 DFS!

 

재귀 함수를 이용하는 대표적인 예로는 팩토리얼 문제가 있다. 팩토리얼 기호는 !를 사용하며 

n!는 1 x 2 x 3 ··· (n-1) x n 을 의미한다.

// 반복적으로 구현
func iterativeFunc(num: Int) -> Int {
    var result = 1
    
    for n in 2...num {
        result *= n
    }
    return result
}

print(iterativeFunc(num: 5)) // 120

// 재귀적으로 구현

func recursiveFunc(num: Int) -> Int {
    if num <= 1 {
        return 1
    }
    return (num * recursiveFunc(num: num - 1))
}

print(iterativeFunc(num: 5)) // 120

위 두 코드를 실행해보면 결과는 120으로 동일하다. 

반복문 대신 재귀 함수를 사용했을때 얻을 수 있는 장점은 재귀 함수가 조금더 간결하고 가독성이 좋다. 이렇게 간결해진 이유는 수학적 점화식을 그대로 소스코드로 옮겼기 때문이다.

여기서 점화식이란 
1. n이 0 혹은 1 일 때  = factorial(n) = 1
2. n이 1보다 클 때 = factorial(n) = n * factorial(n-1)