[Java] 재귀함수

재귀란?

사전적 용어로는 '원래 자리로 되돌아가거나 되돌아옴'이라는 뜻이다.

그렇다면 재귀함수는 사전의 뜻과 비슷하게 함수를 선언할 때 선언한 함수를 그 함수 안에서 계속 호출해주는 메서드라고 할 수 있다.

public void recursion() {
	System.out.println("Hello");
    System.out.println("World");
    recursion();
}

위와 같이 호출하게 되면 출력값이 무한히 반복되는 것을 볼 수 있을 것이다.

재귀함수의 장점

• 불필요한 반복문의 사용을 줄일 수 있어서 코드가 간결해지고, 수정이 용이함
• 변수를 여러개 선언할 필요가 없음

재귀함수의 단점

• 반복문과는 다르게, 코드의 흐름을 직관적으로 파악하기 어려움
• 반복문에 비해 많은 메모리 사용
• 메서드를 호출하고 메서드가 종료된 이후, 복귀를 위한 컨텍스트 스위칭 비용 발생

재귀함수를 사용하기 위한 조건

• 문제를 점점 작은 단위로 쪼갤 수 있어야 함
• 재귀 호출이 종료되는 시점이 존재해야 함

아래 예제는 재귀함수를 사용한 예제 들이다.

---

N까지의 합

class SumFunction {
	public static void main(String[] args) {
    	int N = 5;
    	System.out.println("1부터 N까지 의 합 : " + Sum(N));
    }
    
    public static int Sum(int num) {
    	if (num == 1) {
        	return 1;
        }
        return num + Sum(num - 1);
    }
}
// 출력
15

구구단

class GugudanFunction {
	public static void main(String[] args) {
    	Gugudan(2, 1);
    }
    public static void Gugudan(int level, int count) {
        if (count > 9) return;

        System.out.printf("%d x %d = %d", level, count, level * count);
        Gugudan(level, ++count);
    }
}
// 출력
2 x 1 = 2
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
2 x 6 = 12
2 x 7 = 14
2 x 8 = 16
2 x 9 = 18

피보나치 수열

class FibonacciFunction {
	public static void main(String[] args) {
   	   int N = 5;
	   System.out.println(Fibonacci(N));
    }
    
    public static int Fibonacci(int num) {
    	if (num <= 1) {
        	return num;
        }
        
        return Fibonacci(num - 1) + Fibonacci(num -2);
    }
}
// 출력
5