[펌_java를 이용한 자료구조] 재귀(Recursion)

LONG

===============================================================================================

 

재귀에게는 뭔가 위험한게 있다.

하지만 재귀함수는 위험한(?) 요소를 가지고 있습니다. 잘만 사용한다면 코드가 간결해지는 이득을 볼 수 있지만, 어설픈 경험을 바탕으로 재귀함수를 여기저기서 사용한다면, 그에 걸맞는 황당한 경우를 당할 수도 있습니다.

첫번째가 바로 Stack Overflow 인데요, 메모리에서 에러가 나는 경우입니다. 프로그램이 죽죠. 지난 강좌에서 Runtime Stack에 재귀함수를 호출할 때마다 쌓인다는것을 알려 드렸죠? 이 Runtime Stack은 또 다른 메모리 영역에 비해서 그 공간이 제한적입니다. 코드를 잘못쳐서 무한에 가깝게 재귀호출을 해버리면 갑자기 Stack Overflow라는 오류가 뜨면서 프로그램이 죽게 됩니다. 컴파일때는 아무 에러메시지가 뜨지 않지만, 실제로 수행해 보면 나게 되는 오류입니다.


[그림 2] Stack Overflow Error
저것이 바로 Stack Overflow Error입니다. 단순히 숫자를 계속해서 하나씩 빼내는 재귀함수 입니다. 100부터 시작을 했는데요, 저정도에서 에러가 나더군요. 물론 저 코드야 간단하니깐 얼마든지 금방 고칠수 있지만 복잡한 코드 내의 재귀호출에서 저런 에러가 뜨면 모니터가 갑자기 노랗게 보이죠. 이런 에러가 나지 않도록 하는게 프로그램을 짜는 사람의 의무 이겠죠.

또 하나는 속도의 저하 입니다. 자료구조는 단지 10개, 100개 정도의 적은 자료를 다루기도 하지만, 매우 많은 양의 자료를 다루기도 합니다. 적은 양의 자료를 다룰때는 재귀를 이용하는데 간단하고 속도에도 그다지 영향이 없지만, 자료의 수가 늘면 늘수록 재귀함수를 이용하여 만들은 기능은 속도가 저하되게 마련입니다. 그래서 이런 어려운 문제를 해결하기 위해서 일부는 DP(Dynamic Programming)개념을 이용하여 해결하기도 합니다. 자세한 것은 알고리즘 강좌를 참고하시면 얻으실 수 있을 것입니다.

위에서 말한 두가지 정도가 있습니다. 이 두가지 경우만 고려해서 재귀를 이용하시면 깔끔한 코드를 작성하실 수 있게 될 것입니다.

강좌를 끝마치며...

이번 강좌는 코드가 많지 않은 강좌가 되었군요! 독자분들이 기뻐하실지, 싫어하실지... 이번 강좌를 통해서 재귀가 무엇인지 알게 되셨다면 충분히 성공하셨다고 자신하셔도 될 것입니다. 아 요즘 날씨가 매우매우 춥군요... 밖에 나가기가 무서울 정도 입니다. 독자여러분들도 감기 걸리지 마시구요~. 다음 강좌때 뵙도록 하겠습니다. 행복한 겨울 보내세요~.

 

 

ARTICLE 참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며...

안녕하세요. 이번강좌는 Recursion에 대해서 배워보게 되겠습니다. 조금만 이해를 잘못하셔도 나중에 꼬이면 해결이 어려워지는 곳이므로 주의해서 강좌를 읽어주시면 감사하겠습니다.

Recursion?? 재귀??

어떠한 작업이 있다고 가정해 보겠습니다. 그것을 해결하려고 반복문을 쓰려다 보니 해결해야 하는 범위는 계속 나뉘어서 작아지지만, 해결하는 과정 자체가 매우 반복적인 일 입니다. 이렇게 되면 중복되는 코드가 많아지고, 조건도 많이 분기되고, 코드가 복잡해 지는것이 보통입니다. 이런 작업에서 주로 재귀를 이용하여 코드를 단순화 시키곤 합니다.

밑의 코드는 Fibonacci number를 구하는 알고리즘인데요, 예시로 반복문으로 짠 경우와, 재귀로 짠 경우를 비교해 보도록 하겠습니다.

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]; }

위와 같은 경우가 바로 반복문으로 짠 Fibonacci number 구하는 코드 입니다. 재귀로도 한번 짜 보겠습니다.

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

[그림 1] Fibonacci number 수 실행화면
일단 다른 것들 보다는 코드가 굉장히 짧아진 것을 한눈에 보실수 있을 것 입니다.

물론 코드가 단순화 되서 보기야 좋지만 단점도 존재합니다.

그것은 뒤에서 더 자세히 다루도록 하겠습니다.

=============================================================================================

 

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); }

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