본문 바로가기

알고리즘/Algorithm

Recursion(순환)-1

반응형

Recursion vs Iteration

 

  • 모든 순환함수는 반복문으로 변경 가능하다.
  • 모든 반복문은 recursion으로 표현 가능하다.
  • 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다
  • 함수 호출에 따른 오버헤드가 존재한다.(매개변수 전달, 액티베이션 프레임 생성 등)

 

자기 자신을 호출하는 함수(메서드)를 Recursion이라고 한다.

 

1
2
3
4
5
6
7
8
9
10
11
public class Code01{
    public static void main(String [] args){
        func();
      }
    
    public static void func(){
        System.out.println("Hello....");
        func();
    }
}
       
cs

 

 

Recursion은 위와 같은 코드를 보면 메서드안에 자기 자신을 다시 호출함으로 무한루프에 빠질 수 있다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Code02{
    public static void main(String [] args){
        int n = 4;
        func(n);
    }
    
    public static void func(int k){
        if(k<=0){
            return;
        }else{
               System.out.pringln("Hello....");
            func(k-1);
        }
    }
}
cs

 

위의 코드를 보면 Recursion이라고 항상 무한루프에 빠지는 것은 아니다. 

 

1
2
3
4
5
6
7
8
Hello...
Hello...
Hello...
Hello...
 
 
 
 
cs

코드의 결과는 Hello...를 4번 반복하고 종료된다. 

 

무한루프에 빠지지 않으려면 2가지 조건을 만족해야 한다.

 

1. Base case : 적어도 하나의 자기자신을 호출하지 않고 recursion에 빠지지 않는 경우가 존재해야 한다.

2.  Recursive case : recursion을 반복하다 보면 결국 base case로 수렴해야 한다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Code 03{
    public static void main(String [] args){
        int result = func(4);
        System.out.print(result);
    }
 
    public static int func(int n){
 
        if(n==0){
            return 0; // n= 0 이면 총 합은 0 이될수 밖에 없다
       }else{
            return n + func(n-1);
    }
}
cs

ex_1 : n개 합을 구하는 메서드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Code 03{
    public static void main(String [] args){
        int result = func(4);
        System.out.print(result);
    }
 
    public static int factorial(int n){
 
        if(n<=0)
            return 1;
        else{
            return n * factorial(n-1);
    }
}
cs

ex_2 : 펙토리얼 구하는 메서드

 

1
2
3
4
5
6
public static int factorial(int n){
        if(n<2)
            return n;
        else{
            return fibonacci(n-1) + fibonacci(n-2);
    }
cs

ex_3 : 피보나치 수열 구하는 메서드

 

1
2
3
4
5
6
7
8
9
10
11
12
public static double gcd(int m, int n){
    if(m<n){
        int tmp=m;
        m=n;
        n=tmp;
    }
    
    if(m%n==0)
        return n;
    else
        return gcd(n, m%n);
}
cs

ex_4 : 최대 공약수 구하는 메서드

 

반응형

'알고리즘 > Algorithm' 카테고리의 다른 글

Recursion의 응용 - 미로찾기  (0) 2021.01.19
2진검색 알고리즘  (0) 2021.01.19
Recursion(순환)-3  (0) 2021.01.19
Recursion(순환)-2  (0) 2020.07.05
선형 시간 알고리즘  (0) 2020.07.05