[자바/Java] 메소드5 - 재귀 호출

재귀란?

재귀 호출, 재귀 함수에서 재귀(recursive)란 자기 자신을 또 다시 호출한다는 뜻이다.

 

즉 재귀 함수(메소드)는 함수(메소드) 내에서 메소드가 자기 자신을 또 다시 호출하는 것이다. 이렇게 재귀를 통해 자기 자신을 호출하는 이유는 복잡한 문제를 간단하고 논리적으로 기술이 가능하기 때문이다.

 

그렇기 때문에 코딩 테스트 문제를 풀다 보면 많이 사용되는 개념 중 하나이다. 여러 복잡한 문제들을 간단하고 논리적이게 표현이 가능하다고는 하지만 메모리 부담이라는 명확한 단점 또한 존재한다.

 

이러한 단점에 대한 이유는 재귀가 어떤게 작동하는 지를 통해 알 수 있다.

 

 

 

재귀의 작동 방식

메소드를 호출할 경우, 호출한 시점에 대한 상태를 메모리에 저장해 두어야 메소드 종료시 현재 상태로 돌아와 남은 작업을 처리할 수 있다.

 

그렇기 때문에, 재귀를 통해 자기 자신을 호출할 경우 호출하기 이전의 상태를 재귀 호출을 할 때마다 stack에 저장하게 되는 것이다. 

 

이 때에, 아래의 예시와 같이 종료조건 없이 무한히 재귀를 호출하게 된다면 stack 메모리를 초과하여 stack overflow 에러가 발생하여 프로그램이 종료되어 버린다.

 

public void printNum(int n) { //stack overflow 발생
    //숫자 출력
    System.out.println(n);
    //1 증가 시킨 숫자 출력을 위한 재귀 호출
    printNum(n + 1)
}

 

 

 

종료 조건

종료 조건이란 말 그대로 끊임 없이 호출되는 재귀를 종료 시킬 수 있는 조건이다. 재귀 함수를 통해 발견하고자 하는 해답을 만났거나 더 이상 재귀를 호출하는 것이 의미가 없는 조건을 만날 경우, return문을 통해 재귀를 종료시키게 되는 것이다.

 

대표적인 재귀함수의 예인 피보나치 수열을 구현하면 다음과 같다.

 

public int fibonachi(int n) {

    if(n == 1 || n == 2) return 1;  //종료 조건
    return fibonachi(n-1) + fibonachi(n-2);
    
}

 

피보나치 수열의 예시를 보면, 재귀를 통해 n-1번째 수와 n-2번째 수를 더하는 것을 볼 수 있다. 만약 종료 조건이 없다면 위의 재귀 함수는 n이 음수를 넘어서 무한히 재귀를 호출하다 stack overflow가 발생하여 종료될 것이다.

 

하지만, 피보나치의 조건 중 하나인 f(1) = 1, f(2) = 1을 통해, 종료조건을 설정해주어 n == 1과 2일 때 재귀를 종료하여 원하는 값을 얻을 수 있게 되는 것이다.

 

위의 예시에서 n이 5일 경우, 작동하는 흐름을 그림으로 나타내면 다음과 같다.

 

 

 

재귀의 구조

재귀의 구조는 위에서 몇 번 언급하였듯이 Stack의 구조를 가지고 있다.

 

Stack은 LIFO(Last-In First-Out)이기 때문에 가장 나중에 들어온 것이 가장 먼저 나간다. 이 때, stack에서 쌓인 것을 다시 빼내는 시점이 바로 종료 조건을 만나 return 되는 시점인 것이다.

 

메소드 내에서 재귀를 호출하면 호출한 메소드의 상태가 stack에 차곡 차고 쌓이게 되고 종료조건을 만나게 되면 쌓인 메소드의 상태들을 불러와 남은 작업을 처리하고 최종적인 결과값을 반환하는 것으로 메소드가 끝나는 것이다.