1. 순환의 개념과 기본 예제 1

무한루프에 빠지지 않으려면

• base case : 적어도 1개의 recursion에 빠지지 않는 경우가 존재해야 함

• recursive case: recursion을 반복하다보면 결국 base case로 수렴해야함

순환함수와 수학적 귀납법

정리: func(int n)은 음이 아닌 정수 n에 대해서 0~n까지의 합을 올바로 계산

1. n=0이라면, 0을 반환한다. 올바르다.

2. 임의의 양의 정수 k에 대해 n<k인 경우 0~n까지의 합을 올바르게 계산하여 반환한다고 가정하자.

3. n=k 인 경우,

   • func는 먼저 func(k-1)을 호출하는데 2번의 가정에 의해 0~k-1까지의 합이 올바로 계산되어 반환

   • 메서드 func는 그 값에 n을 더해서 반환

   • 따라서 메서드 func는 0~k 까지의 합을 올바로 계산하여 반환

Factorial: n!

recursion의 흔한 예시

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

int factorial (int n) {
    if(n==0) {
        return 1;
    }
    return n*factorial(n-1);
}

x^n

x^0 = 1
x^n = x * x^n-1  (if n > 0)

double power(double x, int n) {
    if(n==0) return 1;
    return x * power(x, n-1);
}

fibonacci

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) (n>1)

int fibo(int n) {
    if(n <= 1) {
        return n;
    }
    return fibo(n-1) + fibo(n-2);
}

최대공약수: Euclid method

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

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

간단하게

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