스택과 재귀

재귀함수

사실 재귀함수는 스택메모리에 쌓이는 형태로 동작하므로 모든 재귀함수는 스택으로 손쉽게 변환할 수 있다.
근데 과연 바꾸는게 맞을까?
궁금해서 메모이제이션하지 않은 단순 피보나치 함수로 확인해보았다.

• 30까지의 피보나치 구하기
  
• 40까지의 피보나치 구하기
  

스택이 어느정도 느릴꺼라고 예상은 했지만, 너무 압도적인 성능 차이가 나버렸다.
돌리기 전까지는 힙메모리와 스택메모리의 접근 속도 때문에 느리지 않을까 했는데
이정도의 차이는 그런 문제가 아닌 듯 했다.

꼬리재귀 최적화

재귀함수를 사용 시 특정 컴파일러마다 꼬리재귀 최적화를 수행한다.
아마 위의 성능 차이는 꼬리재귀 최적화로 인한 문제가 아닐까 생각이 된다.

• 꼬리 재귀
  꼬리 재귀란, 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태

  함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리 하도록 알고리즘을 바꿔 스택을 재사용

• 꼬리 재귀 함수 예시

 private static int factorial(int n) {
    return factorialMethod(n, 1);
}
    
private static int factorialMethod(int n, int value) {
    if (n == 1) {
        return value;
    }
    return factorialMethod(n - 1 , value * n);
}

컴파일러는 이러한 함수를 반복문의 형태로 최적화시켜버린다.

int factorialMethod(int n) {
   int value = 1;
 
   do {
     if (n == 1) 
       return;
     value = value * n;
     n = n - 1;
   } while(true);
}

테스트 시 사용한 코드

import java.io.*;
import java.util.Stack;

public class Main3 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        long start = System.currentTimeMillis();
        int fb = fb(N);
        long end = System.currentTimeMillis();
        long start1 = System.currentTimeMillis();
        int fb1 = fb_stack(N);
        long end1 = System.currentTimeMillis();
        System.out.println("피보나치 재귀 : "+fb+" 시간 : "+(end-start)/1000.0);
        System.out.println("피보나치 스택 : "+fb1+" 시간 : "+(end1-start1)/1000.0);
    }

    static int fb(int n){
        if(n ==1) return 1;
        if(n==2) return 2;
        else return fb(n-2) + fb(n-1);
    }

    static int fb_stack(int n){
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(n);
        while(!stack.isEmpty()){
            int value = stack.pop();
            if(value == 1){
                ans+=1;
            }
            else if(value == 2){
                ans+=2;
            }
            else{
                stack.push(value-1);
                stack.push(value-2);
            }
        }
        return ans;
    }
}

꼬리재귀 최적화를 위해서는 꼬리 재귀를 할 때 연산자를 적용하지 않아야 꼬리 재귀를 하는 것처럼 안내되어 있지만, 다른 곳에서는 특정 언어, 특정 컴파일러에서는 어떠한 연산자는 사용해도 최적화를 해주는 경우도 있다고 하였다.
아마 위의 테스트코드의 경우에도 + 연산자를 넣더라도 최적화를 해주는 게 아닐까 생각한다.

추가

반복문의 퍼포먼스는 Integer 범위를 초과할때까지 책정할 수 없을 정도로 빨랏다.
꼬리재귀 최적화가 정말로 된다면 아마 이와 같을 테니, 이러한 꼬리재귀의 이유도 아님을 알 수 있었다.
어떠한 이유일지 추가적으로 공부가 필요할 것으로 보인다.

더하여, Memoization을 한 피보나치 재귀 함수도 반복문과 같이 Integer 범위까지 퍼포먼스 테스트를 할 수 없었다.