자료구조 11 - 재귀 알고리즘(1)

재귀 알고리즘에 대해서 학습하려고한다

 

재귀 (recursive) 의 사전적정의 : 어떤것을 정의할때 자기자신을 참조하는 것을 뜻함

-->프로그래밍에서도 그대로 사용된다

다음의 재귀의 대표적인 예시인 팩토리얼 코딩을 보자

 

int factorial(n){

           if(n>0)

                     return n*factorial(n-1);

           else

                     return 1;

}

위 처럼 간단하게 작성할 수 있다

 

return n*factorial(n-1) 파트가 재귀가 사용된 그림인데 아래에 도식화 된 그림을 참조하자

 

다음과 같이 재귀적으로 코드가 실행 된다.

위에서 return 1; 은 중요한 파트로 없으면 안되는 부분이다 

 

위의코드를 앞에서배운 스택과 연계하여 생각할수 있는데 ==>(재귀와 스택의 연관성)

factoral(5) -> factoral(4) -> factoral(3) -> factoral(2) -> factoral(1)  -> factoral(0) 으로 스택에 값이 쌓이고

값이 사용될땐 factorial(0) -> factoral(1) -> factoral(2) -> factoral(3) -> factoral(4) -> factoral(5) 순서대로 값이 사용된다.

 

그 다음으론 재귀용법을 통해서 최대공약수를 뽑아내는 코드를 작성해 보았다

import java.util.Scanner;

class GCD{

           public vstatic int GCD(int a,int b){

                     int k =0;

                     if(a<=b){

                                for(int i =2; i<=a; i++){

                                           if(a%i ==0 & b%i ==0){

                                                      k = i;

                                                      break;

                                           }

                                }

                     }

                     else{

                                for(int i=2; i<=b; i++){

                                           if(a%i==0 & b%i==0){

                                                      k = i;

                                                      break;

                                           }

                                }

                     }

 

                     if(k==0)

                                return 1;

                     else

                                return k*GCD(a/k,b/k);

 

           }

 

           public static void main(String[] args){

                     Scanner scan = new Scanner(System.in);

                     System.out.println("최대공약수구하기 위한 첫번째 수는?");

                     int a = scan.nextInt();

                     System.out.println("두번째 수는?");

                     int b = scan.nextInt();

                      

                     System.out.println("최대 공약수는 : "  +GCD(a,b) + "입니다");

 

 

           }

}

GCD.java

0.00MB

위의 코드에서 a와 b를 굳이 대소비교 할필요없지만 a와 b의 값이 차이가 많이나는경우 계산낭비를 줄이기위해 조건문을 걸어 놓은 것이다.

아래의 도식화된 그림으로 위의 재귀알고리즘에 대해서 설명을 하겠다.

 

위의 그림을 통해서 어렵지 않게 이해할 수 있다.

 

여기서도 재귀와 스택개념을 연결지어서 이해하면 좋을것 같다

 

그리고 재기와 반복문은 겉으로 보기엔 비슷해보이지만

반복문은 조건문이 참인동안 반복을 진행하는 것이고

재귀는 기본형태로 다가가면 반복이 끝나는 것이다

위에서 return 1; 이 나타내는 것이 기본형태 라고 보면 된다.

 

다음시간은 재귀알고리즘 추가내용과 하노이탑에대해서 다루어보겠다.