[알고리즘] Recursion 이란 - 2

Recursion(재귀) 이란  

앞서 우리는 피보나치나, 최대공약수등의 수학적 계산에 대한 예제를 살펴보았다.

그렇다면 Recursion은 수학적 계산에만 유용한 것일까

그렇지 않다.

우리는 일반적으로 for나 while등의 반복문을 이용하여 문제를 푸는데,

이는 모두 재귀함수로 풀어낼수 있다.

예제를 살펴보자

문자열의 길이 찾기

if this string is empty
    return 0;
else
    return 1 plus the length of the string that                                                             
        excludes the first character

슈도(의사) 코드로 작성한 문자열의 길이 찾기이다.

문자의 길이가 0이라면 0을 리턴하고

길이가 0이 아니라면 하나의 문자열을 제외한 문자열의 길이 +1을 리턴한다.

public static int length(String str){
    if(str.equals(""))
        return 0;
    else
        return 1+length(str.substring(1));                                                                   
}
 

이를 코드화 하면 위와 같다.

자바의 substring 함수를 이용하여 앞을 제외하고 문자열을 자른다.

재귀적으로 str이 0이 될때까지 순환하여 구현한다.

문자열을 하나씩 출력

public static void printChars(String str){                                                                     
    if(str.length()===0)
        return;
    else{
        System.out.print(str.charAt(0));
        printChars(str.substring(1));                                                          
    }
}
 

문자단위로 문자열을 출력하는 코드이다.

String기본 내장 함수인 charAt으로 가장 앞쪽의 문자를 선택하여 출력한다.

str값이 없어지면 리턴되며 함수의 순환은 종료된다.

문자열을 거꾸로(Reverse) 출력

public static void printCharsReverse(String str){                                                            
    if(str.length()===0)
        return;
    else{
        printCharsReverse(str.substring(1));
        System.out.print(str.charAt(0));
    }
}
 

문자열을 거꾸로 출력하려면 어떻게 해야할까

위의 코드와 2번째 예제를 비교해 보면 else내부의 문장의 순서만 바뀐것을 알수있다.

재귀 내부에서 함수 호출과 일반 문장의 순서가 바뀌면 일어나는 재미있는 예제이다.

손으로 직접 그림을 그려보며 증명해보기 바란다.

2진수 출력하기

public void printInBinary(int n){                                                                           
    if(n<2)
        System.out.print(n);
    else{
        printInBinary(n/2);
        System.out.print(n%2);
    }
}
 

입력으로 하나의 정수를 받은 후 2진수로 변환하여 출력하는 예제이다

어떤 n이라는 정수를 받아서 2진수로 바꾸게 되면

마지막 비트는 0이거나(짝수) 1이된다(홀수).

마지막 비트는 n을 2로 나누었을때가 마지막 비트이다.

마지막 비트를 제외한 비트들은 n을 2로 나누었을때의 몫이다.

즉, n을 2로 나누었을때 몫을 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은 데이터의 개수이므로 0보다 작거나 같을때 0을 반환한다.

그렇지 않으면 n-1까지의 데이터를 더한 후, n-1번째 데이터를 더해주면 된다.

Recusion vs Iterator

- 모든 재귀 함수는 반복문(iterator)로 변경 가능

- 그 역도 성립한다. 즉, 모든 반복함수는 재귀 함수로 표현이 가능하다

 - 재귀 함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는것이 가능하다

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

출처: 부경대 권오흠 교수님, 영리한 프로그램을 위한 알고리즘 강좌