8-2-4.재귀 호출

메서드는 언제나 누구든지 호출할 수 있다. main에서만 호출하는 것이 아니라 메서드끼리 서로 호출하여 작업을 분담시킨다. main에서 methodA를 호출하고 methodA는 실행중에 다시 methodB를 호출하는 식으로 호출 단계는 얼마든지 깊어질 수 있다.

호출을 받은 메서드는 작업을 마친 후 정확하게 원래 위치로 돌아온다. 이런 식으로 메서드끼리 인수를 전달하고 리턴값을 반환하는 식으로 주거니 받거니 통신하면서 작업을 처리한다. 각 메서드가 세부 작업을 담당하므로 main은 순서에 맞게 메서드를 호출하여 전체적인 흐름만 관장하면 된다.

메서드 호출의 특수한 예는 자기가 자신을 다시 호출하는 재귀 호출이다. 메서드끼리 서로 호출하는 것 뿐만 아니라 자기 자신을 호출할 수도 있다. 큰 문제를 잘게 나누어 점진적으로 해결하는 기법(Divide & conquer)으로 종종 사용된다. 재귀 호출의 가장 대표적인 예는 누승을 구하는 것인데 간단한 예제로 구경만 해 보자.

recursive	실행결과
class JavaTest { public static void main(String[] args) { System.out.println("5 팩토리얼 = " + factorial(5)); } static int factorial(int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); } } }	5 팩토리얼 = 120

누승 n!은 1~n의 곱을 구하는 연산으로 정의되어 있다. n!은 n*(n-1)!로 더 잘게 나눌 수 있으며 1!은 더 볼 것도 없이 1이다. 이 점을 활용하여 factorial 메서드는 인수로 전달받은 n이 1이 아니면 n과 (n-1)!로 문제를 분할하여 자기 자신을 다시 호출한다. 인수의 값을 하나씩 줄여 1이 될 때까지 반복하면 누승이 구해진다.

자기 자신을 호출하더라도 조건문에 의해 언젠가는 끝나도록 되어 있어 무한 호출은 아니다. 누승은 재귀 호출의 가장 전형적인 예이지만 꼭 재귀 호출이 아니라도 구현 가능하다. 그러나 디렉터리 계층 순회나 트리 검색처럼 본질적으로 재귀적인 형태를 가진 자료 구조를 다룰 때는 재귀 호출이 꼭 필요하다.