[스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
• [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

거듭제곱: Power (3 / 6) in Swift4

• 거듭제곱이 뭐야?
• by 나무위키

• 재귀호출 요구사항 재귀호출에 대해 모른다면 클릭
• 재귀의 호출은 문제 내에서 범위가 점점 작은 방향, 즉 하위문제에 대해 이루어 져야 한다.
• 재귀 호출은 더 이상 반복되지 않는 종료 조건이 있어야 한다. 

• 거듭제곱 재귀호출 과정
• by khanacademy

$x^n$x, start superscript, n, end superscript을 계산하려고 한다고 가정합시다. 여기서 $$xx는 임의의 실수이고 $$nn는 임의의 정수입니다. $$nn이 0이라면 $$xx의 값이 무엇이든 간에 $$x^0 = 1x, start superscript, 0, end superscript, equals, 1이기 되기 때문에 문제는 쉽습니다. 이는 좋은 탈출 조건입니다.

그러면 이제 $$nn이 양수일 때 어떻게 되는지 알아봅시다. $$xx의 거듭제곱을 곱할 때는 지수를 더하면 됩니다. 임의의 밑수 $$xx와 임의의 지수 $$aa와 $$bb에 대해 $$x^a \cdot x^b = x^{a+b}x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript입니다. 그러므로 $$nn이 양수이고 짝수이면 $$x^n = x^{n/2} \cdot x^{n/2}x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript이 됩니다. $$y = x^{n/2}y, equals, x, start superscript, n, slash, 2, end superscript을 재귀적으로 계산하고자 할 경우 $$x^nx, start superscript, n, end superscript을 $$y\cdot yy, dot, y로 계산할 수 있습니다. $$nn이 양수이고 홀수일 경우는 어떨까요? 그러면 $$x^n = x^{n-1} \cdot xx, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x이고 $$n-1n, minus, 1은 0이거나 짝수인 양수가 됩니다. 방금 지수가 0이거나 짝수이면서 양수일 때 $$xx의 거듭제곱을 계산하는 방법을 알아보았습니다. 이제 $$x^{n-1}x, start superscript, n, minus, 1, end superscript을 재귀적으로 계산하고 이 결과를 이용하여 $$x^n = x^{n-1} \cdot xx, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x를 계산할 수 있습니다.

$$nn이 음수일 경우는 어떨까요? 그러면 $$x^n = 1 / x^{-n}x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript이고 지수 $$-nminus, n은 양수가 됩니다. 그러므로 $$x^{-n}x, start superscript, minus, n, end superscript를 재귀적으로 계산하고 그 역수를 구하면 됩니다.

• 정리하면
• n = 0 이면  x0=1 ( 종료조건 )
• n > 0 양수일 때
• n 이 짝수면  
•  $$x^n = x^{n/2} \cdot x^{n/2}xn=xn/2⋅xn/2x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript 로 계산, 다시 xn/2 을 재귀 호출
  
  
• n 이 홀수면
•  $$x^n = x^{n-1} \cdot xx, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x
• n < 0 음수일 때 
• $x^n=1/x^{-n}$x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript 로 계산하므로  $$x^{-n}x, start superscript, minus, n, end superscript을 재귀적으로 계산하고 그 역수를 구하면 되겠쥬?
• 구성
• 전체 구성을 보고 큰그림 그리세요.
• 재귀호출, 반복문으로 이렇게 2개 구현할 예정입니다.

public func example( description:String, excute:()->() ) // 실행시킬 때 사용할 메소드
public func processTime(description:String, blockFunction: () -> ()) // 실행시간 측정할 때 사용할 메소드.
 
public func power_recur(x:Double, n:Int) -> Double // 재귀호출로 구현한 거듭제곱.
public func power_for(x: Double, n: Int) -> Double // 반복문으로 구현한 거듭제곱.

• 구현 : power_recur
• 재귀호출로 구현한 거듭제곱
• 거듭제곱 정의에 의해n = 0 이면  x0=1 이 재귀호출의 종료조건이 됩니다. -> 요구사항 1 만족
• 반환을 자기 자신을 호출하는 재귀호출로 하는데 매개변수에 n  / 2  혹은 n - 1 입력되쥬? 반 씩, 1 씩 작아지므로 - > 요구사항 2 만족
• 거듭제곱 에서  $x^n$은 x 를 n 번 곱하는 것이기 때문에 $x^1$ 을 n 번 곱하는 것이 되쥬? 결국 홀수의 경우에서 모두 처리되는 것.
• 음.. 다른 곳에서 반환되는 모든 재귀호출이 홀수의 경우로 모두 모인다는 말인데. 더 쉽게 설명할 순 없을까...

public func power_recur(x:Double, n:Int) -> Double {
    if n == 0 { return 1 } // 요구사항 1 -> 종료조건. 
    else if n > 0 { // 양수
        if n % 2 == 0 { return power_recur(x: x, n: n / 2) * power_recur(x: x, n: n / 2) } // 짝수
            // 짝수
            // 요구사항 2 -> 재귀호출의 매개변수에 n / 2 이다. n 이 1 / 2 씩 작아짐.
        else { return x * power_recur(x: x, n: n-1) }
            // 홀수
            // 요구사항 2 -> n - 1 이므로 n 이 -1 씩 작아짐
    }else { return 1 / power_recur(x: x, n: -n) } // 음수 
}
 

• 구현 : power_ for
• 반복문으로 구현한 거듭제곱
• 반복문은 반복의 범위가 정해지기 때문에 n 이 곧 종료조건이 되겠쥬? 
• 재귀보다 더 간단하게 구현되쥬? 재귀로 구현한게 무색합니다. 이럴거면 재귀왜해? 라는 생각이 드는 시점일 텐데
• 이것과 반대로 반복문은 엄청 복잡한데 재귀로 구현하면 단 몇 줄 만으로 구현할 수 있는 것들도 있습니다. 그래서 재귀 하고 있는거에요^^

public func power_for(x: Double, n: Int) -> Double { 
    if n == 0 { return 1} // 종료조건
    else{
        var result: Double = 1 
        for _ in 1...n { result = result * x }
        return result
    }
}

• 실행 과 결과

실행시간은 1초도 안되지만 굳이 비교해 보자면 반복문으로 구현한 것이 4배정도 더 빠르네요

• Helper 메소드 ( 궁금하실 까봐^^.. ) 

public func example( description:String, excute:()->() ) {
    print("---Example of \(description)---")
    excute()
}
 
public func processTime(blockFunction: () -> ()) -> Float { 
    let startTime = CFAbsoluteTimeGetCurrent() 
    blockFunction() 
    let processTime = CFAbsoluteTimeGetCurrent() - startTime 
    return (Float(processTime))
}

전체 소스 코드