[Algorithm] Java의 재귀(Recursion) 함수

🎯 목표 : 재귀 함수의 이해와 활용

📒 재귀 함수

---

📌 특징

• 자기 자신을 호출 하는 메소드.
• 주어진 문제를 작은 단위로 쪼개며 최소 단위(Base Case)에 도달 하였을때, 최소 단위 에서 부터 순차적으로 연산을 하며 메소드를 빠져 나오는 형태로 구현한다. 이때 최소 단위에 도달 하였을때 순차적으로 연산을 시작 할수 있게 메소드 호출을 끝내는 브레이크 포인트 같은 부분이 반드시 필요하다.
• 재귀 함수의 장점으로는 불필요한 여러개의 반복문을 사용하지 않고 여러개의 변수를 사용하지 않아 코드가 간결해지며, 수정에 용이하다.
• 단점으로는 코드의 흐름을 직관적으로 파악하기 어려우며, 중복적인 메소드 호출에 따른 메모리에 부담으로 프로그램의 성능이 현저히 떨어지게 된다. 또한, 메소드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다.
• 컨텍스트 스위칭이란 대기와 실행을 반복하는 것이고, 그에 따른 비용은 기존 실행 프로세서를 우선 순위에서 미루고, 새 프로세스로 교체할때 프로세서 상태값을 교체 하는 작업을 말한다.

---

📌 구현 - 팩토리얼 (for문과 비교)

• 가장 대표적인 재귀 함수 예제인 팩토리얼을 for문과 비교해 구현 해 보았다.

public class RecursiveFunction {
//     5! = 5*4*4*3*1 = 120

    public static int factorialFor(int num){ // for문 팩토리얼 구현
        int sum = 1;
        for(int i = 2; i<=num; i++){
            sum*=i;
        }
        return sum;
    }

    public static int factorialRecursion(int num){  // 재귀 함수 팩토리얼 구현
        if(num == 1)return 1; // Base Case
        // num의 값이 1일때 예상하기 쉬운 케이스 이므로 1을 반환한다.
        else return num*factorialRecursion(num-1);
        // Recursive Case
    }
}

• 팩토리얼은 주어진 숫자를 1부터 주어진 숫자까지 모든 수를 곱한 값을 의미 한다.

• 위 코드에서 재귀함수로 팩토리얼을 구현하였을때, 위 그림을 보면, 1 팩토리얼 ( 1! ) 에 해당하는 부분이 Base Case로 볼수 있다.
• 1 팩토리얼의 값은 1을 가지고 2 팩토리얼이 연산될때 1팩토리얼 값인 1이 적용되어 2와 연산하게 되고 2팩토리얼 값은 2를 가지게 된다, 또다시 3 팩토리얼이 연산될때 2 팩토리얼 값이 3과 연산되며 3팩토리얼 값은 6을 가지게 된다. 이처럼 순차적으로 Base Case에서 부터 연산되어 최초 메소드 호출 Case까지 연산되면 메소드는 종료된다.
• 위 코드에서 num 값이 1일때 1을 반환하는 Base Case를 선언 하지 않았더라면, 팩토리얼 메소드는 무한 루프에 빠지게 된다. \= StackOverflowError 재귀함수를 정의할때 주의 해야한다.

---

📌 구현 - 피보나치 수열

• 재귀 메소드의 원리를 조금 더 확실히 이해하기 위해 대표 예제인 파보나치 수열을 재귀 메소드로 구현 했다.

 public class RecursiveFunction {
  	public static int fib(int number) {
        if(number <=1) return number;
        else return fib(number-1)+ fib(number-2);
    }

    public static void main(String[] args) {
    System.out.println(fib(5)); // 파보나치 수열의 5번째 원소를 출력
    }
}

• 피보나치 수열은 첫번째 1 두번째 1 로 시작되며 첫번째와 두번째 수를 계속 더하며 증가하는 규칙이고, 5번째 수는 5가 된다.
• 1, 1, 2, 3, 5, 8, 13, 21

• 코드와 그림을 보면, 피보나치 수열의 5번째 수를 구하기 위해서는 4번째 수와 3번째 수를 알아야되며, 4번째 수를 구하기 위해서는 3번째 수와 2번째 수를 알아야되고......필요한 수를 구하기 위해 앞의 수와 그 앞의 수를 구하는 메소드를 호출 하게된다. 
• 이 처럼 하나의 재귀 메소드 내에서 두번의 재귀 메소드를 호출하게 되고, 위 코드에서는 num<=1 이라는 Base Case 선언을 해 두었기 때문에 F(1), F(0)까지 호출 되지 않는다. 하지만 구하고자 하는 수가 커지면 호출해야되는 메소드는 기하 급수 적으로 증가하게 될것이다. 
• 재귀 메소드의 기본 원리를 이해하기 위해 간단히 구현 해 보았고, 30번째 피보나치 수열의 수를 찾기 위해서는 위 메소드를 2,692,537번 호출해야 찾을수 있었다.

---

📌 구현 2 - 피보나치 수열(꼬리 재귀)

• 30번째 피보나치 수열의 수를 찾기 위해서 재귀 메소드를 2,692,537번 호출 해야하는 상황을 개선할 방법이 없는지 찾아 보다 꼬리 재귀 함수 구현 방식이란 개념을 훑었다.
• 꼬리 재귀란 return으로 함수를 실행할 때 Base Case 도달 했을때, 순차적으로 연산을 하며 돌아오지 않고 반환값만 돌려주는 방식이다.
• 하지만, 이 방법으로는 피보나치 수열 재귀 메소드의 실행 횟수를 줄일수는 있지만, Java에서 Tail Call을 제대로 구현할수 없다. Java 8 컴파일러 레벨에서는 Tail-Call Optimisation(TCO)를 지원하지 않는다.
• 즉, 피보나치 예제에서는, 메소드의 호출 횟수만 줄어들 뿐 메소드 호출 단계별 계산 결과를 각 호출 Stack에 저장해두는 점은 똑같다. 이는, 팩토리얼 예제에서도 동일하게 적용되며 꼬리재귀 방식으로 팩토리얼을 구현하게 되면, 개선되는 부분은 없다는 것이다. (피보나치는 재귀 메소드 각 단계에서 2번 호출, 팩토리얼 예제는 재귀 메소드 각 단계에서 1번 호출)
• 이 부분을 람다와 함수형 인터페이스로 구현할수 있는 방법이 있다고 하지만 추후에 심화적으로 학습 예정이다.
  Reference :  https://blog.knoldus.com/tail-recursion-in-java-8/
• 꼬리 재귀 방식으로 피보나치 수열을 구현 하고 메소드 호출 횟수를 확인 해 보았다.

public class RecursiveFunction {
    private static int countFibTail =0;
    private static int countFib =0;
    public static void main(String[] args) {
        System.out.println("30 th fibonacci : "+fibonacciTail(30,0,1));
        System.out.println("fibonacciTail : "+ countFibTail);
        System.out.println("30 th fibonacci : "+fibonacci(30));
        System.out.println("fibonacci : "+ countFib);
    }
    public static int fibonacci(int number) {
        countFib++;
        if(number <=1) return number; // Base Case
        else return fibonacci(number-2)+ fibonacci(number-1);
    }
    public static int fibonacciTail(int input, int before, int after) {
        countFibTail++;
        if(input <=1) return after; // Base Case
        else return fibonacciTail(input-1,after,before+after);
    }
}
/*
 출력값
30 th fibonacci : 832040
fibonacciTail : 30
30 th fibonacci : 832040
fibonacci : 2692537
*/

• fibonacciTail 메소드 에서는 피보나치 수열에서 시작하기 위한 0과 첫번째 수 1을 매개변수로 지정하여 주었으며, 재귀 메소드 내부에서 return값으로 fibonacciTail 메소드를 재귀 호출 할때 다음 연산에 필요한 피보나치 수열의 두개의 수를 매개 변수로 지정해주는 방식으로 특별한 연산 없이 Base Case를 향해 재귀 메소드를 호출하게 하였다.
• Base Case에 도달했을때의 반환값은, 최종으로 구하고자 하는 피보나치 수열의 수를 반환하게 하였고, 최초 호출 재귀 메소드로 돌아오며 특별한 추가 연산 없이 돌아올수 있게 되지만, 각 재귀 메소드의 호출 Stack에 단계별 계산 결과를 저장하는 것은 동일하다.
• 두번의 재귀 메소드 호출을 해야되는 것을 한번으로 줄어 든 것을 확인할수 있으며, 꼬리 재귀 방식으로 개선 되었다고 할수 있을거 같다.
• 하지만, 의도하고자 한 Tail-Call Optimisation(TCO)기능은 구현되지 않았다.