재귀 알고리즘

“Factorial n”을 구하는 재귀 알고리즘을 작성하시오.(90회 정보관리 기술사)

 

 1. 재귀알고리즘의 개념

가) 재귀알고리즘의 정의

- 수학적 귀납법을 역순으로 이용하여 자신의 함수를 반복적으로 호출하는 방법

나) 재귀알고리즘의 구성 분할 정복	문제의 크기가 N인 큰 문제를 작은 문제로 환원, 이때 작은 문제 역시 큰 문제와 유사함
재귀 호출	Self Call, Boomerang
아주 작은 문제	직접 해결할 정도로 작아짐, 베이스 케이스가 됨

 

 2. 재귀 알고리즘의 작성 절차 및 효율성

가) 재귀 알고리즘의 작성 절차

Step1	- 더 작은 문제로 표시할 수 있는지 시도(문제 크기를 하나씩 줄이는 방법, ,반으로 줄이는 방법, 다른 여러 개의 작은 문제의 조합으로 표시하는 방법) - 문제 크기 파라미터 N을 확인
Step 2	문제를 직접 풀 수 있는 것이 어떤 경우인지 베이스 케이스 확인
Step 3	- N이 줄어서 반드시 베이스 케이스를 만나는지 확인 - N이 양수인지 음수인지, 짝수인지 홀수인지, 또는 부동소수인지 정수인지 모든 경우에 대해 모두 검증.
Step 4	베이스 케이스와 베이스 케이스가 아닌 경우를 나누어서 코드를 작성

 

 나) 재귀 알고리즘의 효율성

- 공간적 비효율(저장공간)

- 시간적 비효율(저장, 복원에 걸리는 시간)

- 가능하다면 반복문으로 대치하는 것이 유리

 

3. 문제에서 제시한 Factorial n 에 대한 풀이

 

가) 문제에 대한 해석

n! = n • (n-1) • (n-2) • ... • 1 (단, 1! = 0! = 1)

 

int Factorial(int n)

 

{           if (n = = 1)

return 1;

else

return(n * Factorial(n-1));

}

 

나) 코드로 구현

int Factorial(int n) 　　　　　　　　　　　　　팩토리얼 { int product = 1; 　　　　　　　　　　　　　곱셈의 결과 값을 초기화 for (int i = 1; i <= n; i++) 　　　　　　　　　　1부터 n까지 product *= i; 　　　　　　　　　　　　　　　계속 곱해서 저장 return product; 　　　　　　　　　　　　　　결과를 리턴 }

 

4. 재귀 알고리즘의 이용

- 이진 탐색 : 문제 크기의 감소, N, N/2, N/4, … , 1

- 문자열 뒤집기

- K 번째 작은 수 찾기

- 피보나치 수열

“끝”