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

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

Recursive Thinking; 순환적으로 사고하기

1. Recursion은 수학 함수 계산에만 유용한가?

→ 다른 많은 문제들을 recursion으로 해결할 수 있다

많은 예제들

• 문자 개수 세기
• 문자열을 뒤집어 출력하기
• 2진수로 변환하여 출력
• 배열의 합 구하기
• 데이터 파일로 부터 n개의 정수 읽어 오기
• ...

1. 2진수 변환 출력 예제

    // 4. 2진수로 변환하여 출력
    func printBinary(n: Int) {  // 음이 아닌 정수 n을 이진수로 변환하여 인쇄한다
        if n < 2 {
            print(n, terminator: "")
        } else {
            printBinary(n: n / 2)   // n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
            print(n % 2, terminator: "")    // n을 2로 나눈 나머지를 인쇄한다
        }
    }

    printBinary(n: 5)

2. 배열의 합 구하기 예제

    // 5. 배열의 합 구하기
    // data[0]에서 data[n-1] 까지의 합을 구하여 반환한다.
    func sumArray(n: Int, data: [Int]) -> Int {
        if n <= 0 {
            return 0
        } else {
            return sumArray(n: n - 1, data: data) + data[n - 1]
        }
    }

    let result4 = sumArray(n: 4, data: [0, 1, 2, 3])
    print("\n배열의 합 구하기 예제 결과 : \(result4)")

2. Recursive vs Iteration

• 모든 순환 함수는 반복문(iteration)으로 변경 가능
• 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능
• 순환 함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함
• 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)