순환(Recursion)

순환(Recursion) : 자기 자신을 호출하는 함수 (= 재귀함수)

Q. 어떻게 되나? (what will happen?)
A> 무한 루프
Q. 항상 무한루프에 빠질까?
A> 어떻게 작성하느냐에 따라 달라진다
, 그래서 순환을 쓸 때 매개변수와 return을 이용해서 무한루프를 방지한다.

무한루프에 빠지지 않으려면
Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
Recursive case : recursion을 반복하다 보면 결국 base case로 수렴해야 한다.

< 1 ~ n까지의 합 >

순환함수와 수학적귀납법
정리 : func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.
증명 :
1. n=0인 경우 : n=0인 경우 0을 반환한다 (Base case)
2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정하자
3. n=k인 경우를 고려해보자. func은 먼저 func(k-1)을 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반한된다. 메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.

Factorial: n!

0! = 1
n! = nx(n-1)! n>0

순환함수와 수학적귀납법
정리 : factorial(int n)은 음이 아닌 정수 n에 대해서 n!을 올바로 계산한다.
증명 :
1. n=0인 경우 : n=0인 경우 1을 반환한다. 올바르다 (Base case)
2. 임의의 양의 정수 k에 대해서 n<k인 경우 n!을 올바르게 계산한다고 가정하자.
3. n=k인 경우를 고려해보자. factorial은 먼저 factorial(k-1) 호출하는데 2번의 가정에 의해서 (k-1)!이 올바로 계산되어 반환된다. 따라서 메서드 factorial은 k*(k-1)! = k!을 반환한다.

X^n

X^0 = 1
X^n = X*X^n-1 if n>0

Fibonacci Number

f0 = 0
f1 = 1
fn = fn-1 + fn-2 n>1

최대공약수 : Euclid Method

m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n) = n이고, 그렇지 않으면 gcd(m, n) = gcd(n, m%n) 이다.

public static double gcd(int m, int n) 
{
	if(m<n) { int tmp = m; m=n; n=tmp; } // swap m and n
    if(m%n == 0)
    	return n;
	else
    	return gcd(n, m%n);
}

Euclid Method : 좀 더 단순한 버전

gcd(p,q) = p (if q=0) / gcd(q, p%q) otherwise

public static int gcd(int p, int q)
{
	if (q==0)
    	return p;
    else
    	return gcd(q, p%q)
}