Recursion(2)

[EKOO의 JAVA를 이용한 자료구조:8회] Recursion(2)

저자:EKOO| 날짜: 2005년 06월 02일

 

Runtime Stack에 쌓이는 재귀함수

보통 프로그래밍을 하다보면 여러가지 변수 선언을 많이 하게 됩니다. 이런 변수들이 메모리에 잡히는 것은 이미 다들 아시겠죠? 재귀 함수가 호출되면 전달된 Parameter와 지역변수가 Stack에 쌓이게 됩니다.

설명을 위하여 간단한 재귀함수를 하나 만들어 보겠습니다. 이것을 이용해서 Runtime Stack에 재귀함수가 어떻게 쌓이게 되는지 살펴보도록 하죠.

public static void Recursive_function(int number) {     System.out.println(number);     number = number - 1;     Recursive_function(number); }

위와 같은 재귀함수가 하나 있다고 가정해 보겠습니다. Recursive_function(100); 이라고 호출을 해보면 어떻게 될까요? 아마도 화면엔 100, 99, 98, 97... 계속해서 숫자가 하나씩 감소해 가면서 화면에 찍히게 될 것입니다. Recursive_function 함수의 세번째 줄 코드를 보시면 자기 자신을 부르죠? 저렇게 재귀호출을 하는 것입니다. 이것은 메모리에 아래와 같은 그림처럼 쌓이게 됩니다.

1. Recursive_function 함수 호출

2. Recursive_function 함수 내에서 한번 재귀호출

3. 2번의 상태에서 다시 Recursive_function 함수 재귀호출
[그림 2] Runtime Stack에 쌓이는 재귀함수
위의 그림처럼 재귀함수는 메모리 영역의 Stack에 쌓이게 됩니다. 그림처럼 달랑 변수만 쌓이는것은 아니구요 스택포인터 같은 것들이 더 쌓이게 됩니다. 하지만 자세한것은 넘어가도록 하겠습니다. 제목에서 말하는 Runtime stack은 프로세스 실행시에 로컬 변수나 파라메터 전달을 위해 사용하는 메모리 입니다. 이곳에 변수들이나 스택포인터를 위한 공간이 잡히게 되겠죠.

위의 함수는 무한정 계~속 재귀호출을 하겠죠? 보통 재귀함수를 작성할때는 조건을 두어 재귀호출을 하게 되지만, 그 조건을 잘못 준다거나 실수를 하여 무한정 재귀호출을 하면 Stack 이라는 메모리 공간이 꽉 차서 Stack Overflow 라는 에러 메시지를 볼 수 있습니다. 메모리 영역에 대해서 더 궁금하시다면 '전광성의 어셈블리어 강좌 8장'을 참고하시면 좀더 자세한 정보를 얻으실 수 있습니다.

메모리에 대한 얘기는 여기에서 끝내도록 하구요, 이제 이 재귀함수로 어떤것을 작성 할 수 있는가에 대해서 살펴보도록 하겠습니다.

재귀를 이용하여 무엇을 할까요?

과연 이 복잡한 재귀함수를 이용하여 어떤 것을 만들 수 있을까요? 사실 재귀함수는 자료구조 라고는 할 수 없습니다. 하지만 자료구조에서 다루는 이유는, 재귀를 이용하여 구조를 만들어 내고 분석하고, Traverse등을 쉽게 할 수 있기 때문입니다.

재귀는 알고리즘에서도 많이 쓰입니다. 이 말은? 즉 위에서 한 말처럼 특정 자료구조를 쉽게 다루기 위한 알고리즘에서 재귀를 쓰면 된다는 말이겠죠? 지난번 Tree 강좌를 다시한번 상기해 보시면, Binary Search Tree를 만들어 보신거 기억 하시죠? 클래스의 멤버 함수들 중에 트리의 모든 노드를 방문하는 함수 3가지가 있었었습니다. preorder, inorder, postorder의 방식으로 모든 노드를 방문하는데 이 함수들이 각각 재귀함수로 짜여졌습니다. 물론 재귀를 이용하지 않고도 가능하지만 그렇게 되면 코드도 복잡해지고, 작성하기가 까다로워서 주로 재귀를 이용하는게 통상적인 방법입니다.

public int Fibonacci_1(int number) {     System.out.print("fib[" + number +"]" + " : " );     int i;     int[] fib = new int[number + 1];     fib[0] = 0;     if( number > 0 )     {         fib[1] = 1;         for( i = 2 ; i <= number ; i++ )             fib[i] = fib[i - 1] + fib[i - 2];     }     return fib[number]; }

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

앞에서도 예시로 들은 두 코드 입니다. 확실히 코드가 짧아진걸 한눈에 보실수 있습니다.