[알고리즘]_순환(Recursion)_1 개념 및 예제

부경대학교 권오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘'

---

 

순환(Recursion)이란?

자기 자신을 호출하는 함수

void funtion(){
	...
    function();
}

 

---

Recursion이 무한루프에 빠지지 않으려면?

Base case와 Recursive case가 필요

Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

Recursive case : recursion을 반복하다보면 결국 Base case에 수렴해야 한다.

public int func(int n) {
	if(n==0) // Base case n==0일 경우
		return 0; // 0을 반환
	else
		return n+func(n-1); // Recursive case
}

 

---

 

Factorial: n!

시간복잡도 : O(n)

public int factorial(int n) {
	if(n==0) // Base case n==0일 경우
		return 1; // 1을 반환 0!==1
	else
		return n*factorial(n-1); // Recursive case
}

---

 

Xⁿ

시간복잡도 : O(n)

public double power(double x, int n) {
	if(n==0) // Base case n==0일 경우
		return 1; // 1을 반환 X⁰==1
	else // n>0의 경우
		return x*power(x, n-1); // Recursive case 
}

---

 

최대공약수: Euclid Method

m>=n인 두 정수 m, n에 대해 m이 n의 배수이면 gcd(m, n)=n, 즉 m과 n의 최대공약수는 n이고,

그렇지 않으면 gcd(m, n)=gcd(n, m%n)이다.

public double gcd(int m, int n) {
	int tmp=m;
	if(m<n) // m보다 n이 더 큰 경우 m과 n의 값을 바꿔줌 
		tmp=m; m=n; n=tmp;
	if(m%n==0) // m이 n의 배수일 경우
		return n; // m과 n의 최대공약수는 n
	else
		return gcd(n, m%n);
	}

 

좀 더 간단한 버전

n==0이면 gcd(m,n)은 n이고, 그렇지 않으면 gcd(n,m%n)

public double gcd(int m, int n) {
	if(n==0) 
		return m;
	else
		return gcd(n, m%n); 
}