재귀함수

재귀함수(Recursive Call)

재귀함수란 함수에서 해당 함수를 반복적으로 호출하는 함수를 말하며

대표적인 예시로는 팩토리얼 함수가 있으며 아래 진행방식과 코드로 작성된다.

 

팩토리얼 함수 진행방식

1! = 1

2! = 1! x 2

3! = 2! x 3

 

코드

func factorial(num: Int) -> Int {
    if num < 2 { return num }
    return factorial(num: num - 1) * num
}

print(factorial(num:3)) // 6

위 팩토리얼 코드가 동작하는 과정을 살펴보면 3을 num 파라미터로 전달하여 factorial 함수를 호출했으므로 

1. factorial(num:2) * 3

2. factorial(num:1) * 2

3. factorial(num:0) * 1

위 순서대로 메모리에 저장되고 3번째 함수가 동작할 때 num 값이 1 < 2를 만족하므로 1을 반환하게 된다.

이때부터 위 그림처럼 역순으로 팩토리얼 함수의 결과값을 반환하게되는데 순서는 아래와 같다.

1. factorial(num: 0) * 1 -> 1

2. factorial(num: 1) * 2 -> 2

3. factorial(num: 2) * 3 -> 6

최종적으로 factorial(num: 3)의 결과값은 6이 된다.

 

재귀함수에서 필수적으로 구현해야할 부분은 

첫번째 탈출 조건을 정확하게 명시해주어야 한다. 탈출 조건을 명시해주지 않는다면 무한루프에 빠지게 되므로 주의해야한다.

두번째 재귀함수의 핵심이라고 할 수 있는 함수를 다시 호출하는 부분을 빼먹지 않도록 주의해야한다. 

세번째 반환값 

 

위 세가지 필수 조건을 기본적으로 구현해야 재귀함수가 완성된다.

func factorial(num: Int) -> Int { // 반환 타입 
    if num < 2 { return num } // 탈출 조건 
    return factorial(num: num - 1) * num // 함수 호출 
}