재귀 함수(Recursive Function) - 중급 편

재귀 함수를 공부하는데 있어 가장 중요한 방법은 코드를 작성하기 전, 생각하는 것이다. 나는 코딩을 처음 배울때 다른 사람이 코드 작성하는 것을 따라가기 급급했고, 생각하는 습관을 형성하지 못했다. 단순한 문제 같은 경우는 생각하지 않아도 자연스럽게 코드가 작성되는 문제가 있지만, 나는 생각하는 개발자가 되고 싶었었고, 이 습관을 고치는데 굉장히 오랜시간이 걸렸다.
앞으로 제시할 두 문제는 재귀 함수를 공부하는데 있어 꼭 풀어봐야하는 문제라고 생각한다. 코드를 보기전에, 한번 생각해보면서 재귀 구현 원리를 이해했으면 한다.

1) 팩토리얼(Factorial) 구해보기

팩토리얼은 차례로 곱한다는 뜻으로, 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 n!로 나타낸다.
팩토리얼을 구하는 방법에는 다양한 것이 존재하지만, 여기서는 재귀 함수를 이용해서 구해보려고 한다.

0! = 1

1! = 1

2! = 2

3! = 6

n! = n * (n-1)!

와 같이 정의된다.

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 변수 선언 및 입력:
        int n = sc.nextInt();
        
        System.out.print(factorial(n));
    }
}

⭐️ 결과 
입력 : 5
출력 : 120

2) 피보나치(Fibonacci numbers) 구해보기