[swift] 재귀함수

---

재귀함수란?

• 재귀함수는 함수가 자기 자신을 다시 호출하여 반복하는 함수이다.
• 무한 반복이 되지 않도록 명확한 탈출 조건이 필요하다.
• 재귀함수의 사용의 단점은 스택오버플로우가 발생할수 있다는 것이다.
  (자기 자신을 다시 호출할 때 그 호출 수가 너무 많아지면 발생할 수 있는 문제이다. 재귀함수의 진행방식이 호출할 때마다 스택을 쌓는 방식이라 일정량을 넘으면 스택오버플로우가 발생한다.)
• 스택오버플로우 극복은 '꼬리재귀함수'를 이용할 수 있다.

  ---

예제( 팩토리얼 계산 )

1. 반복문 이용

func factorial (_ n : Int) -> Int {
    var answer = 1
    for i in 2...n {
        answer = answer * i
    }
    return answer
}
print(factorial(4)) 
// answer = 1 * 2 = 2
// answer = (기존 answer = 2) * 3 = 6
// answer = (기존 answer = 6) * 4 = 24
// return 24

2. 재귀함수 이용

func factorialRecursive (_ n : Int) -> Int {
    if n == 1 { return 1 }
    return n * factorialRecursive(n - 1)
}

print(factorialRecursive(4)) 
// 4 * factorialRecursive(3)
// 3 * factorialRecursive(2)
// 2 * factorialRecursive(1)
// n==1 이므로 1 return
//
// 2 * (factorialRecursive(1) = 1) = 2 
// 3 * (factorialRecursive(2) = 2) = 6
// 4 * (factorialRecursive(3) = 6)  = 24

3. 꼬리재귀함수 이용

재귀함수에서 호출 수가 너무 많아져서 스택오버플로우 가 될 수 있음을 방지 하기위해 계산의 누적을 담는 answer 파라미터를 추가한다.

// 꼬리재귀함수
func factorialTailRecursive(_ n: Int, _ answer: Int) -> Int {
    if n == 1 { return answer }
    return factorialTailRecursive(n-1, n * answer)
}

print(factorialTailRecursive(4, 1))
//factorialTailRecursive(4, 1)
//factorialTailRecursive(3, (4*1))
//factorialTailRecursive(2, (3*(4*1)))
//factorialTailRecursive(1, (2*(3*(4*1))))
//n == 1 이므로 return answer
//24

---

참고사이트
https://seolhee2750.tistory.com/58
https://seolhee2750.tistory.com/65