[Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 개념과 기본 예제 1

재귀호출 함수에는 위처럼 무한 반복을 멈추게 하는 조건문을 가진 Base case와,

Base case에 수렴할 때까지 반복되는 행동이 있는 Recursive case로 나뉜다.

 

 

 

예제 1.  팩토리얼 (Factorial)

위 사진처럼 공식화(?) 해두고 프로그래밍하면 좋은 것 같다.

 

 

 

예제 2. X의 n승 (X^n)

 

 

 

예제 3. 피보나치 수열 (Fibonacci)

코드

import java.util.Scanner;

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

    public static void main(String[] args) {
        System.out.println(fibonacci(4));
    }
}

 

 

 

예제 4. 최대공약수 (Euclid Method)

코드

import java.util.Scanner;

public class example {
    public static 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);
    }

    public static void main(String[] args) {
        System.out.println(gcd(2, 6));
        System.out.println(gcd(2, 7));
    }
}

 

 

 

예제 5. 최대공약수 단순ver

코드

import java.util.Scanner;

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

    public static void main(String[] args) {
        System.out.println(gcd(2, 6));
        System.out.println(gcd(2, 7));
    }
}