[JAVA]재귀(Recursion)

재귀 : 자신을 정의할 때 자기 자신을 재참조하는 방법 (=자기호출)

* 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법

 

재귀적 구조 : 어떤 문제 안에 크기만 다른 성격이 똑같은 작은 문제가 포함
예) factorial
n! = n * (n-1)!
예) 수열의 점화식
a(n) = a(n-1) + 2

---

* 대부분의 순환은 반복으로 바꾸어 작성할 수 있다.

 

<factorial - 반복적인 방법>

public static int factorial(int num) {
        int result = 1;
        for(int i = num; i > 0; i--) {
            result *= i;
        }
        return result;
}

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        
        System.out.println(num+"! = " + factorial(num));
    }
 
    public static int factorial(int num) {
        if (num == 1)
            return 1;
        
        return num * factorial(num - 1);
    }
 
}

입력 : 5

출력 : 5! = 120

 

facotrial 만 놓고 비교해보면 재귀함수를 사용한 경우가 간결하다.
재귀함수를 사용하면 반복문을 사용하는 것보다 속도가 빨라지며, 가독성이 높아진다.