Recursion의 개념과 예제

1. 순환이란?

자기 자신을 호출하는 함수 (재귀함수)

void func(){
	...
    func()
    ...
}

 

* 아무 조건없이 호출하면 무한루프에 빠짐 

 

무한루프에 빠지지 않는 조건

-base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야함.

- recursive case:  recursion을 반복하다보면 base case로 수렴해야함.

 

순환을 사용하면 수학함수나 반복문을 편리하게 풀 수 있다. 

 

2. 순환을 이용한 수학함수 계산

순환은 수학적 귀납법을 활용하는데 사용할 수 있다...! 이렇게 생각해본적 없는데 신기하다. 

 

1) 1~n까지의 합

// 1~n 까지의 합
public class recursion {
    public static void main(String[] args) {
        int result = func(4);
    }

    public static int func(int n){
        if(n==0){
            return 0;
        }else{
            return n + func(n-1);
        }
    }
}

 

2) n! (Factorial)

같은 방식으로 함수를 만들 수 있음 

0! =1

k! = k*(k-1)! 

public static int fac(int n){
        if(n ==1){
            return 0;
        }else{
            return n*fac(-1);
        }
    }

 

3) X^n

x^n

x^0 =1

x^n = x*x^n-1 

public static double power(int x, int n){
        if(n ==0){
            return 1;
        }else{
            return x*power(x, n-1);
        }
    }

 

4) 피보나치수열

f0 = 0

f1 = 1

fn = fn-1 + fn-2  (n>1)

public static int fibonacci(int n){
        if(n<2){
            return n;
        }else{
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }

5) 최대공약수 (유클리드 호제법)

m>=n 인 두 양의 정수 m 과 n에 대해서 m이 n의 배수이면 gcd(m,m)=n 이고,
그렇지 않으면 gcd(m,n)=gcd(n,m%n)이다. 

 

5-1) 

( if m<n ) int tmp = m; m=n; n=tmp;

( if m%n ==0) return n;

(else) return gcd(n, m%n);

 

5-2) 단순ver.

gcd(p,q) 

( if q=0 ) = p

( otherwise ) gcd(q, p%q) 

 public static int gcd(int p, int q){
        if( q == 0){
            return p;
        }else{
            return gcd(q, p%q);
        }
    }

 

 

3. Recursive Thinking (순환적으로 사고하기)

반복문대신 recursion을 사용하여 편리하게 문제를 풀 수도 있다. 

 

모든 순환함수는 반복문으로 변경 가능하고, 

모든 반복문은 순환함수로 표현 가능

 

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

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

 

순환을 사용하여 문제를 풀때는 이런식으로 생각하면 된다.

	//문자열의 길이 계산
    public static int length(String str){
        if(str.equals("")){
            return 0;
        }else{
            return 1 + length(str.substring(1)); //1 + 첫 글자를 제외한 나머지 자리수
        }
    }

    //문자열 프린트
    public static void printChars(String str){
        if(str.length()==0){
            return ;
        }else{
            System.out.print(str.charAt(0)); // 맨앞 글자를 프린트
            printChars(str.substring(1)); // 맨 앞 글자를 뺀 나머지를 프린트
        }
    }

    //문자열을 뒤집어 프린트
    public static void reversePrintChars(String str){
        if(str.length()==0){
            return ;
        }else{
            printChars(str.substring(1)); //맨앞글자를 빼고 나머지를 인쇄
            System.out.print(str.charAt(0)); // 맨 앞글자를 그 뒤에 인쇄
        }
    }

    //이진수로 변환하기
    public void printInBinary(int n){
        if(n<2){
            System.out.print(n);
        }else{
            printInBinary(n/2); //n울 2로 나눈 몫을 2진수로 변환
            System.out.print(n%2); //n을 2로 나눈 나머지 
        }
    }

    //배열의 합 구하기
    public static int sum(int n, int[] data){
        if(n<=0){
            return 0;
        }else{
            return sum(n-1 , data) + data[n-1];
        }
    }

    //데이터파일로부터 n개의 정수 읽어오기 
    public void readFrom(int n, int[] data, Scanner in){
        if(n==0){
            return;
        }else{
            // n개의 정수를 data[0], ... , data[n-1] 에 저장
            readFrom(n-1, data, in);
            data[n-1] =in.nextInt();
        }
    }