순환함수 (재귀함수)

순환함수 (Recursion) : 알고리즘이 자기 자신을 반복적으로 호출하는 함수

​

간단한 예제

}

public class Recursion 
{ 
   public static void main(String [] args) {
    
    	int n = 4; 
        func(n); 
} 

public static void func(int k) 
{ 
    if (k<=0) // base case 
        return; 
	
    else 
    { 
        System.out.println("hello"); // Recursion case 
        func(k-1); 
}

}

위의 if(k<=0)과 같이 base case가 있어야 무한루프를 돌지 않는다

무한 루프에 빠지지 않으려면 ?

- Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다

- Recursion case : recursion을 반복하다보면 결국 base case로 수렴해야 한다

​

적용된 예

​

대표적으로

​

* Factorial

int factorial(int n) 
{ 
     if(n <= 1) 
        return 1; 
     else 
        return (n * factorial(n-1)); 
}

​

* 피보나치 수열

피보나치 수는 수학에서 위의 점화식으로 정의되는 수열이다.

피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 .....

int fibonachi (int n) {
    if (n = 0) return 0; 
    if (n = 1) return 1; 
    else 
       return (fibonachi(n - 1) + fibonachi(n - 2));
}

 

- 하노이 타워

막대 A 에 있는 원판을 C로 옮긴다

다음의 조건에 의해서

​

- 한번에 하나의 원판만 이동 가능

- 맨위의 원판만 이동 가능하다

- 크기가 작은 원판위에 큰 원판을 올릴 수 없다

- 중간의 막대를 임시적으로 이용 가능 그러나 위의 조건을 지켜야 함

원판의 크기 순으로 1 ,2 ,3 으로 명명하면

​

가장 작은 1을 A에서 C로 옮긴다

2를 A에서 B로 잠시 옮겨놓는다

C로 옮겨두었던 1을 B로 잠시 옮겨둔다

3을 A에서 C로 옮긴다

B에 옮겨두었던 1을 A로 옮긴다

2를 B에서 C로 옮긴다

A에 있던 1을 C로 옮긴다

​

이 7 단계의 과정을 단순하게 생각해보면

1 ,2 A > B

3 A > C

1,2 B > C

3과정으로 나눌 수 있다

​

따라서

식으로

​

.n개의 원판이 있을 경우

n-1개의 원판을 B로 이동

n번째의 원판을 C로 이동

n-1개의 원판을 C로 이동

void hanoiTower(int n , char A , char B , char C)
{
   if (n = 1) {
    System.out.println(n + ":" + A + ">>" + C)
   }else{
    hanoiTower(n-1,A,C,B);
    System.out.println(n  + ":" + A + ">>"+ B);
    hanoiTower(n-1,B,A,C);
    }
}

public static void main(String [] args)
{
  hanoiTower(4,'X','Y','Z');
  return 0;
}

모든 순환함수는 반복문(iteration)으로 변경 가능

그역도 성립함 , 즉 모든 반복문은 recursion으로 표현 가능

순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함

하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, 액티베이션 프레임 생성)