[알고리즘] Recursion(재귀함수)

💡 재귀함수를 공부하기 전, 함수에 대해 복습하고 넘어가자

• 하나의 기능을 수행하는 일련의 코드를 함수라고 한다.

반환타입 함수명(매개변수){
    
       return `반화타입과 같은 데이터`;
}

혹은

반환타입 함수명(입력){
    
    return 출력;
  }

로 보면 편하다.

ex. 숫자를 문자로 변환하는 함수

    public static String numberToString(int a){
        return "[숫자] : " + a;
    }

    //////////////////////////////////////////////////////////////
    
    // 오버로딩에 대한 것 : calc라는 같은 이름을 써도! 
    // 매개변수의 갯수나 타입에 따라 자동으로 매칭된다.
    
    public static int calc(int a,int b){
        return a*b;
    }
    
    public static int calc(int a, int b,int c){
        return a*b+c;
    }
    
    public static int calc(int a, int b,double c){
        int ret = (int)(c * 10);
        return (a*b)+ret;

💡 재귀함수란?

• 재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
• 특정 분기까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 사용한다.
• 흔히 알고 있는 반복문은 for, while 등이 있는데, 이러한 반복문으로 구현가능한 로직은 모두 재귀함수로도 가능하고 그 반대 역시 가능하다.

대표 예시 1 - 팩토리얼

int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

• 5라는 값을 넣는다면? 5 x 4 x 3 x 2 x 1이 값이 된다.
• 함수를 호출할 때마다 함수의 매개변수,지역변수,반환주소값등을 모두 저장하게 된다.
• factorial(5)를 호출하게되면 반환타입 부분에서 5 * factorial(5-1) 이 수행되면서 factorial(4)가 호출되고 반환을 기다리게된다.
• 그 다음에는 factorial(4) 에 대한 지역변수, 매개변수, 반환주소값등이 콜스택에 쌓이게되는데, 이렇게 factorial(5), factorial(4), factorial(3), factorial(2), factorial(1) 까지 차곡차곡 콜스택이 쌓이게 되고, factorial(1)에서 if(n == 1)이라는 분기에 걸리면서 드디어 해당 콜스택이 하나씩 수행되며 사라질 것이다.

대표 예시 2 - 피보나치 수열

public static int fibonacci(int index) {//5
        if (index == 1) {
            return 1;
        }
        if (index == 2) {
            return 1;
        }

        int value = fibonacci(index - 1) + fibonacci(index - 2);
        //fibonacci(2)+fibonacci(1) + fibonacci(2)  + fibonacci(2)+fibonacci(1)

        return value;
    }

• n이 1이 될때까지 지속적으로 피보나치 함수를 재귀적으로 호출하여 계산하는 것을 볼 수 있다.

재귀함수의 장, 단점

장점

1. 변수를 여럿 만들 필요가 없다.
   ex. 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.

2. while문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다.

단점

1. 지속적으로 함수를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야한다. 그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게 되고, 이는 속도 저하로 이어진다.

2. 함수 호출 → 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.