자바(Java)에서의 재귀함수(Recursive Function) 예제

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 팩토리얼(Factorial)

- 팩토리얼은 5! = 5 * 4 * 3 * 2 * 1을 뜻한다.

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		int N = 5;
		int result = fact(5);
		
		System.out.println(result); // 120출력
		
	}
	
	public static int fact(int N) {
		//기본 파트
		if(N<=1) return 1;
		
		//유도 파트
		else return N * fact(N-1);
	}
}

2. 피보나치(fibonacci) 수열

1) 기본 재귀함수

public static int fibo(int N) {
		//기본 파트
		if(N<=1) return N;
		
		//유도 파트
		else return fibo(N-1) + fibo(N-2);
	}

2) 동적 프로그래밍 방법

- 동적 프로그래밍 방법을 사용하는 이유는 피보나치에서 10을 계산하면 중복되는 계산이 존재한다.

- 그래서, 메모이제이션(Memoization)을 사용한다.

- 메모이제이션(Memoization) : 프로그램을 돌릴 때 이전에 계산한 값을 저장하여 다시 계산하지 않도록해서 알고리즘의 성능이나 실행속도를 빠르게하는 것을 말함.

public static int dynamicfibo(int N) {
        //arr 배열을 선언하여 0은 0, 1은 1을 저장하고, fibo를 계산하여 해당하는 arr에 저장
        if(N <= 1) return arr[N];
        else{
            arr[N] = fibo(n-1) + fibo(n-2);
        }
        return arr[N];
    }