자바로 살펴본 재귀 함수의 동작 방법 - 1 (Java Recursive method)

재귀 함수(Recursive method)는 함수(메소드)에서 본인을 다시 호출하는 방법을 의미 합니다.

재귀(Recursive) 호출 방법은 반복문과 비교문을 활용하여 구현해야되기 다소 어려운 기능을 효율적으로 만드는 데 사용됩니다.

처음 접하면 이해하기 어렵고 단단한 벽을 만나는 느낌이라..많은 연습을 통해서 숙달하여야 합니다.

 

먼저 숫자 1을 1씩 증가시켜서 덧샘을 하는 메소드를 살펴 보겠습니다.

public static void main(String[] args) {
    System.out.println("normalSums : "+normalSums(1));    
}

public static int normalSums(int arg) {
    System.out.println("in :  "+arg);
    if(arg > 5) {
        System.out.println("end : "+arg);
        return arg;
    } else {
        System.out.println("out : "+arg);
    }
    return normalSums(arg+1);
}

 

파라미터 arg 값이 5보다 크면 return을 통해 메소드가 멈추게 하였습니다.

만약 5 보다 작으면 normalSums 함수를 파라미터 arg 값에 1을 더한 뒤에 다시 호출하게 하였습니다.

 

위 샘플 코드처럼 본인의 메소드 안에서 메소드를 조건에 의해 호출하는 방법을 재귀(Recursive)라고 합니다.

이러한 재귀(Recursive) 메소드는 무한 반복 현상을 만날 수 있으므로 항상 조건을 통하여 멈추도록 해야 합니다.

이를 실행시켜보면 아래와 같은 사진을 만나게 됩니다.

값이 순차로 증가됨을 볼 수 있습니다.

 

순차적으로 내부의 메소드를 간단하게 호출하는 재귀 함수는 처음 만나면 어려워 하지 않습니다.

그러나 내용을 조금 바꾼 재귀함수(메소드)를 만나면 내용 이해가 어려워 집니다.

기능이 같지만 내용이 다른 메소드를 아래 코드로 살펴 보겠습니다.

public static void main(String[] args) {
    System.out.println("otherSums : "+otherSums(1));    
}

public static int otherSums(int arg) {
    int res = 0;
    System.out.println("in :  "+arg);
    if(arg > 5) {
        System.out.println("end : "+arg);
        return arg;
    } else {
        res = otherSums(arg+1);
    }
    System.out.println("out : "+arg);
    return res;
}

 

otherSums라는 메소드 입니다.

앞에서 살펴본 normalSums 메소드와 다르게 결과 값을 res라는 변수에 담아두고 출력을 하게 되어 있습니다.

이제 이를 실행하여 보면 "방금 전 처럼 in과 out이 1,2,3,4..에 맞추어 출력되겠지" 라고 생각을 하기도 합니다.

음...? 뭘까요?

 

실제로 출력된 결과를 보면 다른 것을 볼 수 있습니다.

in이 1,2,3,4,5,6 순서로 순차적으로 출력된 이후에 out이 내림순으로 6,5,4,3,2,1이 출력되었습니다.

왜 in과 out이 서로 번갈아가면서 출력이 되지 않는 것 일까요?

 

재귀에 의한 메소드 호출 방법은 조건에 의해 마지막 호출이 될 때 까지 계속해서 반복되게 됩니다.

위에서 살펴본 normalSums, otherSums라는 메소드는 return에 의해서 함수가 종료되는 시점 끝까지 동작한 이후에 되돌아 온 것 입니다.

 

이해를 위해 유명한 재귀메소드 한개를 더 살펴보겠습니다.

public static void main(String[] args) {
    System.out.println("fibonacci : "+fibonacci(4));    
}

public static int fibonacci(int N) {
    if (N == 0)	return 0;
    if (N == 1)	return 1;
    return fibonacci(N - 1) + fibonacci(N - 2);
}

 

피보나치 수열을 구현한 메소드 입니다.

피보나치 수열은 숫자의 앞에 값이 뒤에 값에 더하면서 계속해서 증가하는 규칙을 의미 합니다.

예) 0, 1, 1, 2, 3, 5, 8, 13, 21

 - 첫번째 : 0 + 1 = 1

 - 두번째 : 1 + 1 = 2

 - 세번째 : 1 + 2 = 3

 

해당 메소드는 피보나치 수열을 재귀방법을 통하여 구현되어 있습니다.

이를 이제 그림으로 살펴 보겠습니다.

* 참조 : st-lab.tistory.com

 

fibonacci메소드에 숫자 4가 주어지면 fibonacci 메소드는 해당 숫자가 0 또는 1일 때 까지 fibonacci메소드 자신을 계속해서 호출합니다.

처음 4라는 값이 들어오면 3, 2 값으로 각각 fibonacci 메소드를 다시 호출합니다.

3을 호출한 fibonacci 메소드는 다시 2, 1 값으로 fibonacci 메소드를 호출하고,

2를 호출한 fibonacci 메소드는 1, 0 값을 가지고 fibonacci 메소드를 호출한 뒤에 조건문에 의해서 끝나게 됩니다.

이렇게 재귀방법에 의한 호출은 가장 맨 마지막까지 호출 할 수 있을만큼 호출 한 뒤에 호출했던 곳으로 돌아온 뒤에 끝나게 됩니다.

 

마지막으로 하나 더 살펴보겠습니다.

아래는 재귀호출을 검색하면 유명하게 나오는 재귀메소드 입니다.

public static void main(String[] args) {
    System.out.println("factorial : "+factorial(3));    
}

public static int factorial(int i) {
    if (i == 1) {
        return 1;
    }
    return i * factorial(i - 1);
}

 

factorial 라는 메소드 입니다.

해당 메소드는 숫자를 받아서 감소시킨 i 값을 곱하게 되어 있습니다.

메소드를 실행하면 나오는 모습 입니다.

6이라는 값 입니다.

 

가장 마지막 단계까지 내려가 생각을 해야 합니다.

i 라는 숫자는 계속해서 감소합니다.

i가 1인 경우 이전 값은 2일 것 입니다.

i가 2인 경우 이전 값은 3일 것 입니다.

이를 계산하여보면 실제 factorial 메소드는 1 * 2 * 3 이라는 연산을 하였다는 것을 알 수 있습니다.

factorial 메소드를 조금 수정하여 봅니다.

public static void main(String[] args) {
    System.out.println("factorial : "+factorial(3));    
}

public static int factorial(int i) {
    if (i == 1) {
        return 1;
    }
    int tmp = i * factorial(i - 1);
    System.out.println(tmp);
    return tmp;
}

 

이를 실행하면, 2, 6 이라는 값이 나오는 것을 알 수 있습니다.

1이 나오지 않는 이유는 i == 1 이라는 조건에 의해서 동작하지 않았기 때문 입니다.

1*2*3 = 6 이 되었습니다.

 

재귀(Recursive) 라는 동작에서의 가장 어려운 부분이 바로 이처럼 "가장 마지막까지 메소드를 실행한다" 라는 개념이지 않나 싶습니다.

이러한 재귀동작을 응용하여 조금 어려운 알고리즘이 대표적으로 "완전탐색, 순열 알고리즘" 이 있습니다.

이상으로 자바를 통해 재귀호출 방법에 대해 살펴 보았습니다.

잘못된 부분, 이외 좋은 의견 있으면 댓글 또는 메일로 연락주세요. 👻

 

* 자바로 살펴본 재귀 함수의 동작 방법 - 2 (Java Recursive method with 순열) (https://lts0606.tistory.com/511)