재귀 알고리즘

• 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)라고 한다 

 

ex)

• 팩토리얼

static int factorial(int n){
   if(n>0){
      return n*factorial(n-1);
   }
   else{
      return 1;
   }

• 유클리드 호제법

static int gcd(int x, int y){
   if(y==0){
      return x;
   }
   else{
      return gcd(y, x%y);
   }
}

• 재귀 알고리즘 예시 

static void recur(int n){
   if(n>0){
      recur(n-1);
      System.out.println(n);
      recur(n-2);
   }
}


recur(4);

결과값

 

1

2

3

1

4

1

2

 

<하향식 분석 >

 

                                                                                            recur(4)

                                                            recur(3)                   print(4)            recur(2)

                                            recur(2)  print(3)  recur(1)     print(4)        recur(1)     print(2)

                          recur(1)  print(2)    print(3)   print(1)       print(4)        print(1)      print(2)

                          print(1)   print(2)    print(3)    print(1)       print(4)        print(1)     print(2)

 

<상향식 분석> 

 

recur(1) : recur(0) 1 recur(-1)

recur(2) : recur(1) 2 recur(0)

recur(3) : recur(2) 3 recur(1)

recur(4) : recur(3) 4 recur(2) 

 

결과 : 1 2 3 1 4 1 2