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

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

저는 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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

재귀 : recursive (1 / 6)

• 재귀가 뭐야?
• 정의 : ' 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. '
• 영화 '인셉션' 에서는 꿈에서 또 꿈을 꿔서, 꿈에서 꾸는 꿈이라는게 나오는데 이게 재귀를 표현하기 적당하다고 생각해.
• 아래 그림이 재귀호출을 잘 표현한다고 생각해. 봐봐
• 러시아 인형
• 너무 작아서 더 이상 인형을 나눌 수 없을 때 까지 스스로를 분리하는 거야!

• 재귀 함수: recursive function = 재귀호출
• 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출 이라고도 한다.
• 루프문과 변수를 이용하는 반복적 알고리즘은 재귀함수로 표현할 수 있고 그 역도 성립. for 구문으로 바꿔서 표현 가능하다는 말이네.

• 재귀 알고리즘의 핵심
• 어떤 문제를 해결하기 위해 문제의 범위보다 약간 좁은 하위 문제를 해결합니다. 
• 하위 문제에 대한 해답을 이용하여 원래의 문제를 해결합니다.

• 재귀함수를 구현하기 위한 요구사항
• 재귀의 호출은 문제 내에서 범위가 점점 작은 방향, 즉 하위문제에 대해 이루어 져야 한다.
• 작은 문제먼저 해결하고 점점 더 큰 문제를 해결하는게 재귀적 아이디어의 핵심이라고 했쥬?
• 재귀 호출은 더 이상 반복되지 않는 종료 조건이 있어야 한다. ( 종료 조건을 'base case' 라고도 해서 base case 에 도달해야 한다고 합니다. )
• 종료조건이 없으면 무한루프에 빠져서 메모리만 오지게 쓰다가 프로그램 다운 되겠쥬?

• 재귀호출을 반복문과의 관계 ( 재귀호출을 반복문으로 표현하려 할 때 )
• 반복문 또한 재귀호출과 같이 종료조건이 있다.
• 다음 반복하기 전에 문제의 범위를 좁힌다.

• 재귀 호출 예제 ( 웹서핑 하다가 재귀호출 설명하기 좋은 것 같아서  추가 18.10.3 ) 

컴퓨터에 아래와 같은 연산을 명령했어. a = 5 + (3 + (1 + 2)); 그러면 컴퓨터는 시스템 호출 스택을 이용해서 아래와 같이 수행해. 스택0 –> 전체 수식 = 5 +( 괄호) 스택1 – > 첫째 괄호 = 3 + (괄호) 스택2 –> 둘째 괄호 = (1 + 2)  스택 2 에서 (1+2)를 3으로 반환하면 스택 1 에서 3 + (3) 을 반환하고 스택 0 에서 5 + (6) 을 반환해서 a 의 값은 11이 나오는 거야.  이 예제가 재귀의 요구사항을 만족하는지 확인해보자! a 의 값을 계산하기 위해 스택 0 안에 스택 1 을, 스택 1안에 스택 2를 호출함 으로써 문제의 가장 작은 단위인 스택 2부터 해결. a = 5 + (3 + (1 + 2)); 에서 가장 작은 괄호인 (1+2)부터 해결                                               * 요구사항 1 - 문제의 크기가 작은 것부터 해결한다는 재귀의 아이디어 만족 스택 0 까지 모든 값을 반환하면 스택은 메모리에서 제거되요 . 재귀의 종료 조건인 것이죠.  * 요구사항 2 - 종료조건이 있어야 한다. 만족

• 장단점이 있으니까 쓰거나 안쓰겠지?
• 단점
• 사용자들이 재귀를 꺼리게 되는 이유는 이게 반복을 하는 놈인지 아닌지 알기 어렵다는 점.
• 반복문이 대놓고 문장 한가운데서 '이 블록은 반복될 것임'하고 알려주는 것과 다르게 재귀는 별다른 표시없이 혼자 돌게되므로 코드 내에서 가독성이 떨어지게 된다.
• 흐름을 추적하기도 어렵겠다.
• 이런 이유들 때문에 재귀호출을 경험하는 뉴비들은 뇌를 개조당하는 경험을 하게 됩니다.. 저 또한 그러했답니다.
• 장점  
• 코드를 간결하게 표현 가능. 
• 깊이와 범위를 모르는 문제를 해결 가능하다.

• 재귀 호출 예제
• 팩토리얼 값 구하기 (2 / 6)
• 거듭제곱 구하기 (3 / 6)
• 피보나치 수열 구하기 (4 / 6)
• 하노이의 탑 문제 (5 / 6)
• 최대 공약수 구하기 (6 / 6)