영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #1~3

섹션 0. 순환(Recursion)

1-1. Recursion의 개념과 기본 예제 1

 

Recursion : 자기 자신을 호출하는 함수

 

public class Code01{
	public static void main(String [] args){
    }
	public static void func(){
    	System.out.println("Hello...");
        func();
    }
}

 -> 무한 루프에 빠지게 됨

 

recursion은 항상 무한루프에 빠질까? 아니다 

recursion이 항상 무한루프에 빠지는 것은 아님.

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.println("Hello...");
        	func(k-1);
    	}
    }
    
}

 -> Hello가 4번만 출력되고 끝나게 됨

 

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

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

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

이 두 가지 조건을 만족하면 됨.

 

public class Code03{
	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;
        else
        	return n + func(n-1);
    	
    }
    
}

-> 10 이 출력 why? 1~n까지의 합을 구한다.

 

이 함수의 mission은 0~n까지의 합을 구하는 것이다.

n=0이라면 합은 0이다.

n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.(n+ func(n-1))

* 이 논리는 수학적귀납법과 동일

 

 

Factorial : n!

0! = 1

n! = nx(n-1)! n>0

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

X^n

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

피보나치 수열(Fibonacci Number)

f0 = 0

f1 = 1

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

 

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

 

최대 공약수 (Euclid Method)

 - 최대 공약수 구하는 알고리즘 중에 하나는 m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n) = n 이고, 그렇지 않으면 gcd(m,n) = gcd(n, m%n)이다.

 

public static double gcd(int m, int n){
	if (m<n){
    	int tmp = m; m = n; n = tmp; //swap m and n
    }
	if (m%n==0)
    	return n;
    else
    	return gcd(n, m%n);
}

// 두 수중 더 큰 수가 m이라고 가정

 

 

 

1-2. Recursion의 개념과 기본 예제 2 (Recursive Thinking) - 순환적으로 사고하기

Recursion은 수학함수 계산에만 유용? 아니다 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다

 

- 문자열의 길이 계산

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

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

 문자열의 길이가 0이라면 0을 return

그게 아니라면 나머지 문자의 길이 계산 + 1 return

 

- 문자열의 프린트

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

JAVA에서 str.chatAt -> 첫 문자 리턴해주는 메서드

str.substring(1) -> 첫 글자를 제외한 나머지 문자를 printChars !

 

- 문자열을 뒤집어 프린트

(1) 이 문자열을 뒤집어 프린트하려면

(2) 먼저 첫 글자를 제외한 나머지 문자열을 뒤집어 프린트 한 후

(3) 마지막으로 첫 글자를 프린트 한다

 

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

위에 두 개의 차이는 두 문장의 순서가 바뀐 것밖에 없지만 엄청난 차이가 있음.

 

- 2진수로 변환하여 출력

2진수에서 마지막 비트가 0이라는 것 -> 짝수

2진수에서 마지막 비트가 1 -> 홀수

 

음이 아닌 정수 n을 이진수로 변환하여 인쇄한다

 

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로 나눈 나머지를 인쇄
  }
}

 

- 배열의 합 구하기

data[0]에서 data[n-1]까지의 합을 구하여 반환한다

public static int sum(int n, int [] data) {
  if (n <= 0)
    return 0;
  else
    return sum(n-1, data) + data[n-1];
}

 

- 데이터파일로부터 n개의 정수 읽어오기

Scanner in이 참조하는 파일로부터 n개의 정수를 입력받아 배열 data의 data[0], ..., data[n-1]에 저장한다

 

public void readFrom(int n, int [] data, Scanner in){
	if (n==0)
    	return;
    else {
        readFrom(n-1, data, in);
        data[n-1] = in.nextInt();
    }
}

-> 근데 이런식으로 recursion 코드를 구현하는 경우는 거의 없다.

 

Recursion vs Iteration

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

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

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

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

 

1-3. Recursion의 개념과 기본 예제 3 (Designing Recursion) - 순환 알고리즘의 설계

순환적 알고리즘 설계

- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함

- 모든 case는 결국 base case로 수렴해야 함

 

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라

 

- 순차 탐색 (근데 만약에 이 배열이 정렬되어 있으면 이진검색 할 수 있지 )

int search(int [] data, int n, int target) {
  for (int i = 0; i < n; i++)
    if (data[i] == target)
      return i;
  return -1;
}

 -> 이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다.

하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.

 

- 매개변수의 명시화 : 순차 탐색

int search(int [] data, int begin, int end, int target) {
  if (begin > end)
    return -1;
  else if (target == data[begin])
    return begin;
  else
    return search(data, begin+1, end, target);
}

-> 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

이 함수를 search(data, 0, n-1, target)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.

(begin 앞쪽이나 end 뒤쪽에는 관심이 없다)

begin = end : 데이터가 1개라는 뜻

 

- 순차 탐색 : 다른 버전

int search(int [] data, int begin, int end, int target) {
  if (begin > end)
    return -1;
  else if (target == data[end])
    return end;
  else
    return search(data, begin, end-1, target);
}

-> begin이 아니라 end를 옮겨서 검색

 

- 다른 버전

int search(int [] data, int begin, int end, int target) {
  if (begin > end)
    return -1;
  else {
    int middle = (begin + end) / 2;
    if (data[middle] == target)
      return middle;
    int index = search(data, begin, middle-1, target);
    if (index != -1)
      return index;
    else
      return search(data, middle+1, end, target);
  }
}

-> 반으로 나누고 비교하면서 검색 

binary search와는 다름(이진탐색이랑은 다르다)

 

-매개변수의 명시화 : 최대값 찾기

int findMax(int [] data, int begin, int end) {
  if (begin == end)
    return data[begin];
  else
    return Math.max(data[begin], findMax(data, begin+1, end));
}

-> 이 함수의 미션은 data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다. begin <= end라고 가정한다

 

- 최대값 찾기 : 다른 버전

int findMax(int [] data, int begin, int end) { 
  if (begin == end)
    return data[begin];
  else {
    int middle = (begin+end) / 2;
    int max1 = findMax(data, begin, middle);
    int max2 = findMax(data, middle+1, end);
    return Math.max(max1, max2);
  }
}

-> 반 나누면서 최대값 찾는 방식

 

 

- Binary Search

items[begin]에서 items[end] 사이에서 target을 검색한다

 

public static int binarySearch(String[] items, String target, int begin, int end) {
  if (begin > end)
    return -1;
  else {
    int middle = (begin+end) / 2;
    int compResult = target.compareTo(items[middle]);
    if (compResult == 0)
      return middle;
    else if (compResult < 0)
      return binarySearch(items, target, begin, middle-1);
    else
      return binarySearch(items, target, middle+1, end);
  }
}

JAVA에서 비교할 때 target.compareTo 메서드