14 일차

재귀

∙ 재귀 알고리즘 (recursion, 순환)

- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

- 많은 종류의 문제가 재귀적으로 해결 가능

> 피보나치수열, 이진 탐색, 병합 정렬, 퀵 정렬 등

 

∙ 재귀 함수 (recursion function)

- 자기 자신을 다시 호출하는 함수. 순환 함수

- 자기 자신을 완전히 그대로 호출하지 않고, 함수의 인자를 특정한 방식으로 변경하여 호출 (무한 루프에 빠질 수 있기 때문에)

 

∙ 재귀 함수의 구성

- 기저 조건(base case) : 재귀를 종료하기 위한 조건이 있어야 함(종료 조건)

- 재귀 호출(recursive case) : 자기 자신을 다시 호출하는 부분, 재귀를 반복하다 보면 반드시 기저 조건으로 수렴해야 함

 

 

∙ 재귀 알고리즘 - 재귀 함수 작성하기

- 자연수의 합 구하기 : 양의 정수 N이 입력으로 주어질 경우, 1부터 N까지의 합을 반환하는 함수 sum(N)을 작성하시오.

int sum(int n)
{
	if (n == 1)
		return 1;
    else
    	return n + sum(n - 1);
}

int main()
{
	int res = sum(5);
}

 

∙ 재귀 알고리즘 - 재귀 함수의 특징

- 모든 재귀 함수는 반복문을 사용하는 함수로 변환 가능

- 재귀 함수의 장단점

> 장점 : 코드를 간결하게 작성 가능

> 단점 : 디버깅이 어려움, 스택 오버플로우 주의, 반복문 사용 코드보다 낮은 효율

 

- 재귀 함수와 반복문 사용 함수의 연산 시간 비교

> 1부터 n까지의 자연수의 합을 재귀 방법과 반복문 사용 방법으로 각각 계산하고, 그 실행 시간을 비교

> n값은 1부터 20000까지 변화시키면서 입력으로 전달

 

#include <iostream>
#include <chrono>

using namespace std;

// 재귀알고리즘 - 재귀 함수
int sum_recursive(int n)
{
    if (n == 1)
        return 1;
    else
        return n + sum_recursive(n - 1);
}

// 반복문을 이용한 자연수 합 이용
int sum_iterative(int n)
{
    int s = 0;
    
    for (int i = 1; i <= n; i++)
        s += i;
    return s;
}

int main()
{
    {
        auto start = chrono::system_clock::now();
        
        volatile int s = 0; // 컴파일 최적화가 되기 떄문에 volatile 사용
        for (int n = 1; n <= 20000; n++){
            s = sum_recursive(n);
        }
        
        auto end = chrono::system_clock::now();
        auto msec = chrono::duration<double>(end - start).count() * 1000;
        cout << "sum_recursive():" << msec << "ms" << endl;
    }
    {
        auto start = chrono::system_clock::now();
        volatile int s = 0;
        for (int n = 1; n <= 20000; n++){
            s = sum_iterative(n);
        }
        auto end = chrono::system_clock::now();
        auto msec = chrono::duration<double>(end - start).count() * 1000;
        cout << "sum_iterative():" << msec << "ms" << endl;
    }
}