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

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

저자:EKOO| 날짜: 2005년 05월 31일

 

참고서적 : 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 수 실행화면
일단 다른 것들 보다는 코드가 굉장히 짧아진 것을 한눈에 보실수 있을 것 입니다. 물론 코드가 단순화 되서 보기야 좋지만 단점도 존재합니다. 그것은 뒤에서 더 자세히 다루도록 하겠습니다.