Home

Published

- 8 min read

[ Concept ] 재귀함수(recursive function)

Concept Computer Science
img of [ Concept ] 재귀함수(recursive function)

재귀함수(recursive function)

재귀함수는 알고리즘을 공부하려면 이미 잘 작성할 수 있어야 한다. 아주 쉬운 알고리즘이 아닌 이상, 재귀가 필요한 알고리즘이 많기 때문이다. 그리고 거의 알고리즘의 80%정도는 재귀함수로 이루어져 있다.

재귀함수는 큰 문제를 반복 적용 가능한 작은 문제로 나누어 푸는 방법이다. 코드로서는, 어떤 함수가 매개변수만 바꾸어서 자기 스스로를 호출하는 방식으로 구현한다.

함수 호출은 프로그램 메모리 구조에서 스택을 사용한다. 그렇지만 재귀 호출은 반복적인 스택의 사용으로 인해 메모리 및 속도에서 성능 저하가 발생한다. 따라서 입력값이 커질수록 재귀 함수는 반복에 비해 비효율적일 수 있다. 그래서 상황에 맞게 잘 사용할 수 있어야 한다.

그래도 매우 중요하다. 훌륭한 프로그래머중에 재귀함수를 모르는 경우는 없다.

재귀함수의 간단한 예: 피보나치 수열

피보나치 수열부터 보자. 피보나치 수열은 0항부터 시작하여 순차적으로 더해나가는 수열이다.(수학적 귀납법)

수학적 정의로는 다음과 같다.

$F_0 = 0,$ $F_1 = 1,$ $F_n = F_n-1 + F_n-2(n > 1)$

이 내용을 코드로 보면,

   public static int fibonacciRecursive(int number) {
    if(number <= 1){
        return number;
    }
    return fibonacciRecursive(number - 2) + fibonacciRecursive(number - 1);
}

이런 식으로 자기 자신을 호출해나가는 방식으로 구현한다.

재귀함수의 장단점

장점

  • 가독성이 좋다.
  • 코드가 짧다.
  • 각 단계의 변수 상태가 자동 저장된다.
  • 코드 검증도 쉽다.

단점

  • 재귀적 문제 분석 / 설계가 직관적이지 않다.
  • 맹목적인 믿음이 필요하다.
  • 스택 오버플로우가 발생할 수 있다.(재귀함수 호출이 너무 깊은 경우)
  • 함수 호출에 따른 과부하

그러면 성능 문제 때문에 재귀를 작성 안하는게 나은건가?

읽기 쉬운 코드 작성이 기본이다.

기본적으로 재뒤함수를 사용하는 게 나은 방법이다.(가독성이 좋고, 유지보수가 쉬운 코드가 더 중요하다.)

다음과 같을 경우, 반복문으로 변환한다.(모든 재귀함수는 반복문으로 작성 가능하다.)

  • 스택 오버플로가 날 가능성이 있는 경우
  • 성능 문제가 일어날 가능성이 큰 경우
  • 성능 문제가 확인된 경우

그러나, 단점이 없는 재귀도 있다.

꼬리 호출(tail call)

함수 코드의 제일 마지막에서 다른 함수를 호출하는 경우이다.

예를 들어,

   public int calculateSignature(int[] data, int multiplier){
    int[] tempData = new int[data.length];
    for(int i =0; i< data.length; i++){
        tempData[i] = data[i] * multiplier;
    }

    return accumulate(tempData);
}

스택 프레임이 존재하는 이유는

  1. 함수에서 사용중인 변수 값을 유지하기 위해
  2. 타 함수 호출 후 반환되면 스택에 저장했던 값을 되돌려 사용

인데,

이 경우에, 스택 프레임을 유지할 이유가 없다. 타 함수로부터 반환한 후, 더 이상 연산이 없기 때문이다. 그래서 곧바로 호출자로 반환한다.

따라서 스택 프레임에 저장해놓은 변수 값을 재사용하지 않는다. 그리고 이 경우, 컴파일러가 스택 프레임을 따로 안 만드는 최적화를 하기도 한다.

최적화 예시:꼬리 호출 제거(tail cell elimination) 꼬리 호출 최적화(tail cell optimization)

꼬리 재귀(tail recursion)

꼬리 호출이 특수한 경우이다. 마지막에 호출하는 함수(꼬리 호출)가 자기 자신(재귀)인 경우를 말한다. 이 경우에는 꼬리 호출과 똑같은 최적화가 적용된다.

예를 들어, 일단 팩토리얼 재귀 함수를 보자

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

이 알고리즘은 꼬리재귀인가??

아니다. 마지막 명령어가 factorialRecursive()였다면, 꼬리 재귀가 맞을 텐데, n이 곱해지기 때문에 꼬리 재귀가 아니다.

그렇다면 팩토리얼 꼬리 재귀 함수는 어떻게 나와야 할까

   int factorial(int n){
    return factorialRecursive(n, 1);
}

int factorialRecursive(int n, int fac){
    if(n <=1){
        return fac;
    }

    return factorialRecursive(n-1, n * fac);
}

근데 느꼈다시피, 꼬리재귀함수가 읽기가 더 힘들다. 그러나, 이런 식으로 작성된 코드가 종종 보이기도 한다. 이렇게 작성하는 이유는 앞에서 말한 최적화때문에 이렇게 작성한다.

그렇다면 꼬리 재귀 함수를 지원하지 않는 언어 있더라도 꼬리 재귀 함수를 작성할 줄 알아야 한다. 꼬리 재귀는 반복문으로 쉽게 변경이 가능하기 때문에 쓸 줄 알아야 한다.

재귀 함수로 총합 구하기

재귀 함수

   public class Program{
    public static void main(String[] args){
        int sum = sumRecursive(10);

        System.out.println(sum); // 55

        sum = sumRecursive(100);

        System.out.println(sum); // 5050
    }

    private static int sumRecursive(int n){
        if(n <= 1){
            return n;
        }
        return n + sumRecursive(n - 1);
    }
}

꼬리 재귀 함수

보통 꼬리 재귀 함수가 덜 직관적이다. 하지만 이런 식으로 작성된 코드가 종종 보이는데 최적화 때문에 그런 경우가 많다. 만약 꼬리 호출 최적화를 지원 안하는 언어라면 그렇더라도 충분한 의미가 있다. 꼬리 재귀는 반복문으로 쉽게 변경이 가능하다!

   public class Program{
    public static void main(String[] args){
        int sum = sumTailRecursive(10, 0);

        System.out.println(sum); // 55

        sum = sumTailRecursive(100, 10);

        System.out.println(sum); // 5050

    }

    private static int sumTailRecursive(int n, int sum){
        if(n <= 0){
            return sum;
        }
        return sumTailRecursive(n - 1, sum + n);
    }
}