티스토리 뷰

순환(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으로 표현 가능
  • 순환 함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함
  • 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)
도움이 되셨다면.. Buy me a coffeeBuy me a coffee
댓글
댓글쓰기 폼
반응형
«   2020/12   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
글 보관함
Total
143,304
Today
8
Yesterday
94