1. 순환(recursion)
1) 정의: 자신을 정의할 때 자기 자신을 재참조하는 방법
2) 사용 형태: 프로그래밍에 적용한 "함수의 재귀 호출(Recursive call)"의 형태로 많이 사용
3) 재귀 호출(Recursive call)의 종류
(1) 직접 순환(direct call)
: 함수가 직접 자신(이름)을 호출
eg) A(A())
(2) 간접 순환(indirect call)
: 다른 제 3의 함수를 호출하고, 그 함수가 다시 자신(이름)을 호출
eg) A(B(A()))
4) 순환 방식의 적용
(1) 분할 정복(Divide and Conquer)의 특성을 가진 문제에 적합
- 어떤 복잡한 문제를 간단하게 풀 수 있는 직접적인 작은 문제로 분할하여 해결하려는 방법
- 분할된 문제가 원래의 큰 문제와 그 성질이 같은 경우에는, 분할된 문제의 푸는 방법도 동일
따라서, 1️⃣종료 조건이 만족할 때 까지 2️⃣변화된 입력을 받아 3️⃣같은 동작을 계속하며 순환함
5) 순환 함수의 명령문 골격
if(condition of simplest case) then solve directly
else make a recursive funsion call to a simpler case;
- 무한 루프를 돌지 않고 올바른 recursion을 하려면 아래가 모두 충족되어야 함
1️⃣ 함수 이름이 같아야 함
2️⃣ 인자가 감소/증가되는 부분이 있어야 함
3️⃣ 종료가 있어야 함
2. 순환 versus 반복
- 컴퓨터에서 같은 동작을 되풀이 하는 방법은 두 가지
- 순환(recursion): 순환 함수를 반복 호출하는 법
- 반복(iteration): for나 while을 이용한 반복하는 법
대부분의 순환은 반복으로 바꾸어 작성할 수 있다.⭐
1) 순환의 장단점
- 순환적인 문제에서는 문제를 단순화한 자연스러운 방법임
- 함수 호출의 오버헤드 있음
* 오버헤드란?
- 프로그램의 실행 흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때, 추가적으로 시간/메모리/자원이 사용되는 현상
- 예상하지 못하는 자원들이 소모되는 현상
2) 반복의 장단점
- 수행속도가 빠름
- 순환적인 문제에 대해서는 프로그램 작성이 어려울 수 있음
3. 순환 함수의 예제 - Factorial Program
1) 비순환 함수 - 반복문 이용
int factorial(int n)
{
if(n <= 1) return 1;
else return n*factorial_n_1(n-1);
}- 비순환 함수(for나 while 같은 반복 함수)로도 표현 가능
➡️ 표현이 조금 길지만 제어의 흐름이나 실행 과정을 쉽게 이해할 수 있음
- (n-1)!을 구하는 서브 함수 factorial_n_1를 따로 제작하는 경우의 프로그램
2) 순환 함수 - 재귀 호출
int factorial(int n)
{
if(n <= 1) return 1;
else return (n * factorial(n-1));
}- (n-1)!을 현재 작성중인 함수를 같은 이름으로 다시 순환 호출하는 경우의 프로그램
4. 순환 함수의 예제 - 이원 탐색(binary search)
- 이원 탐색: 주어진 탐색키 key 값이 저장된 배열 a[]의 위치(인덱스, mid)를 찾아내는 방법
- Problem: 서로 다른 n개의 정렬된 수가 배열에 저장되어 있을 때, 특정한 값을 찾아라
- Specification of the binary search proble: 다음 배열 a[10]에서 "searchnum == 4"를 찾는 문제
5. 순환 함수의 예제 - 비효율적인 경우
- 피보나치 수열(Fibonacci sequence): 각 항은 바로 직전 두 항의 합으로 만들어짐
eg) 0, 1, 1, 2, 3, 5, 8, 13, ...
=> 순환 호출 횟수가 급증하여 실행 시간을 기준으로 볼 때, 반복 함수(iteration function) 보다 비효율적임
=> 순환적 정의가 순환적 Algorithm으로 문제를 해결하는 데 최적의 방법이 아닐 수도 있다는 것을 보여주는 예제
6. 학습 내용 정리
