1. 순환이란? (what is Recursion?)
수학적 문제를 recursion으로 풀어보기
- Fibonacci Number
- 최대 공약수 2.1 Euclid Method(최대공약수) 2.2 좀더 단순한 버전
2. Recursive Thinking
Recursive Thinking 영상
수학 함수 뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다
- 문자열 길이 계산
- 문자열 프린트
- 문자열 뒤집어 프린트
- 2진수로 변환하여 출력
- 배열 합 구하기
Recursion VS Iteration
-
모든 순환함수는 반복문(iteration)으로 변경가능
- 그 역도 성립! 즉 모든 반복문은 recursion으로 표현 가능
-
순환함수는 복잡한 알고리즘을 단순, 알기 쉽게 표현하는 것을 가능하게 함
- 하지만 함수 호출에 따른 오버헤드가 있음( 매개변수 전달, 액티베이션 프레임 생성 등 )
- 순환에 비해 속도가 손해를 볼 수 있다.
3. Designing Recursion(순환적 알고리즘 설계)
-
적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
- 모든 case는 결국 base case로 수렴해야함
- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야 함
Recursion 기본예제
-
순차탐색 - Iteration
- recursion 함수 매개변수 선언할때 처음 호출하는 상황말고 자기 자신을 호출하는 상황에서의 매개변수를 생각해야 한다 .
- 그래서 예제에 begin, end가 추가가 된것이다.
- 매개변수의 명시화: 순차탐색 - recursion
- 순차탐색: 다른 버전 - recursion
- 매개변수의 명시화: 최대값 찾기 - recursion
- 최대값 찾기: 다른 버전 - recursion
-
Binary Search
- https://www.geeksforgeeks.org/binary-search-in-javascript/
- Recursive Approach, Iterative Approach 두가지 방법이 설명되어 있다.
