[알고리즘] 순환(Recursive) 개념과 기본 예제 1 정리

순환(Recursive) 개념과 기본 예제 1 정리

순환(Recursive)
자기 자신을 호출하는 함수

1. 순환은 항상 무한 루프에 빠질까?

• 단순 호출만 하면 발생 가능

    // 1. 무한 루프 예제
    func infinityLoop() {
        print("Hello, World!")
        infinityLoop()
    }
  
    infinityLoop()

• recursion이 적절한 구조를 가지게 해서 무한 루프에 빠지지 않도록 함

2. 적절한 구조?

    func sum(n: Int) -> Int {
        if n == 0 {  // Base Case - n이 0이면 종료
            return 0
        } else {
        return n + sum(n: n-1)  // Recursive Case - 반복하다가 n이 0이 되는 순간이 온다
      }
    }

• Base Case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함
• Recursive Case : recursion을 반복하면 결국 base case로 수렴해야 함

3. Recursion 해석

recursion을 해석하려면 약간의 요령이 필요

아래 예제는 0부터 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다

예제

팩토리얼 (Factorial: n! )

• 0! = 1
• n! = n * (x - 1)! (n > 0)

    func factorial(n: Int) -> Int {
        if n == 0 {
            return 1
      } else {
        return n * factorial(n: n - 1)
      }
    }