순환(Recursion)의 개념과 기본 예제 1

순환(Recursion)

- 자기 자신을 호출하는 함수

void func(...) {
    ...
    func(...);
    ...
}

- 무한 루프에 빠지지 않게 해야 한다.

---

예제1

public class Code01 {
    public static void main(String[] args) {
        int result = func(4);
        System.out.print(result);
    }
    
    public static int func(int n) {
        if (n <= 0) return 0;
        else return n + func(n-1);
    }
}

- 무한 루프에 빠지지 않고, '10'이 출력된다.

---

예제2 - 팩토리얼

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

---

예제3 - 피보나치 수

public int fibonacci(int n) {
    if (n < 2) return n;
    else return fibonacci(n-1) + fibonacci(n-2);
}

---

예제4 - 최대공약수, 유클리드 호제법

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

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

 

더 단순한 버전

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