재귀함수(Recursive Function)란?

재귀함수에 관련된 글을 읽기전에 함수(function)가 무엇인지 잘 모르면 [JAVA] 함수(Function)란? 을 먼저 읽어보기 바란다.

(물론 재귀함수를 읽으려고 들어온사람이 함수(funtion)이 무엇인지 모르는 분은 없을거라 생각한다)

 

재귀(순환)함수란? 바로 자기 자신을 호출하는 함수를 말한다. 

예를들어 recursion() 이란 함수가 있다면 recursion() 함수 안에 또 recursion()을 호출(자기자신 호출)하는 형태를 말한다.

void recursion() {
 
    ....
    recursion();
    ...
}
 

 

그런데 만약 재귀함수 안에 자기자신을 호출하게 되면 어떤 일이 벌어질까?

public class Main {
 
    public static void main(String[] args) {
        recursion(0);
    }
 
 
    private static void recursion(int i) {
        System.out.println("i =" + i);
        recursion(i+1);
    }
 
 
}

위 코드를 복사하여 실제 실행해보면 i =0, i =1 .... i = 8999 .... 처럼 숫자가 계속 증가형태로 계속 호출된다. 

즉 무한 루프에 빠지게 된다. 

(사실 위 코드를 실행하면 어느정도 실행되다가 StackOverflow 에러가 발생되는데 이해를 위해 무한루프라고 표현했다.)

왜냐하면 자기 자신을 호출하면 그 호출된 함수 안에서 또 자기자신을 호출하고 또 자기자신을 호출하고 반복되기 때문이다.

따라서 재귀함수를 작성할때는 항상 무한루프에 빠지지 않도록 베이스(base) 조건(case)을 반드시 주어야  하는데  베이스 조건(base case)이란 함수가 빠져나갈(리턴될) 조건을 말한다, 

 

위 코드에서 i 가 100보다 큰 경우 자기자신을 호출하지 않고 리턴되도록 처리하고 다시 실행해보자

그럼 i =0, i =1 ... i=100 까지 출력되고 프로그램이 종료될 것이다. 

public class Main {
 
    public static void main(String[] args) {
        recursion(0);
    }
    
    private static void recursion(int i) {
        if(i > 100) {
            return;
        }
        
        System.out.println("i =" + i);
        recursion(i+1);
    }
    
}

즉 재귀함수는 적어도 하나의 recursion 에 빠지지 않는 베이스케이스(base case)가 존재해야 하고 재귀함수는 재귀를 반복하다 보면 결국 베이스케이스로 수렴해야만 한다.

이런 재귀함수는 수학적인 것을 프로그래밍으로 표현할 때 매우 유용한데 몇 가지 를 살펴보자

 

첫번째는 N 까지의 합을 구하는 재귀함수이다.

재귀함수를 잘 구현 하려면 재귀적인 사고를 잘 해야 하는데 예를들어 N 까지의 합은 N 자신 + (N-1 까지의 합)을 구한것과 동일하고

N-1 까지의 합은 N-1 자기자신 +  (N-2 까지의 합)을 구한것과 동일하다.

계속 나가다 보면 최종적으로 2까지의 합은 2 + (1 까지의 합) 으로 수렵된다.

 

public class Main {
 
    public static void main(String[] args) {
        System.out.println(sum(10));
    }
 
    private static int sum(int N) {
        if(N == 0) {
            return 0 ;
        }
 
        return N + sum(N-1);
    }
 
}

두번째는 팩토리얼(factorial) N! 을 구하는 재귀함수이다.

팩토리얼을 구하기위한 재귀함수의 베이스케이스와 재귀적인 케이스는 아래와 같다.

base case : 0! = 1
recursive case : n! = n x (n-1)! , n > 0

public class Main {
 
    public static void main(String[] args) {
        System.out.println(fatorial(3));
    }
 
    private static int fatorial(int N) {
        if(N == 0) {
            return 1 ;
        }
 
        return N * fatorial(N-1);
    }
}

세번째는 Xⁿ을 구하는 재귀함수이다.

Xⁿ구하기위한 재귀함수의 베이스케이스와 재귀적인 케이스는 아래와 같다.

base case : X⁰ = 1
recursive case : Xⁿ = X * X^n-1, if n > 0

public class Main {
 
    public static void main(String[] args) {
        System.out.println(power(3, 3));
    }
 
    private static int power(int X, int N) {
        if(N == 0) {
            return 1 ;
        }
 
        return X * power(X, N-1);
    }
}

 

레퍼런스

▷ [알고리즘] 제1-1강 Recursion의 개념과 기본 예제들 (1/3)