1. 순환(Recursion)

 

순환함수와 수학적 귀납법

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

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

=> 무한루프에 빠짐

 

:순환은 항상 무한루프에 빠질까? -> NO~!

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);
        }
    }
}

 

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

• Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
• Recursive case : recursion을 반복하다보면 결국 base case로 수렴해야한다.

: 이 함수가 하는 일은?

public class Code03 {
	public static void main(String[] args){
    	int result = func(4);
        System.out.println(result);
    }
    
    public static int func(int n){
    	if(n ==0)
        	return 0;
        else {
        	return n+func(n-1);
        }
    }
}

=> 1~n까지의 합
=> 10

 

• 이 함수의 misson은 0 ~ n까지의 합을 구하는 것이다.
• n =0 이라면 합은 0이다.
• n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.

 

 

정리 : func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.

 

1. n=0인 경우 : n=0인 경우 0을 반환한다. 올바르다.

2. 임의의 양의 정수 k에 대해서 n<k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정하자.

3. n=k인 경우를 고려해보자. func은 먼저 func(k-1) 호출하는데 2번의 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.

 

 

Factorial : n!

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

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

 

정리 : factorial (int n)은 음이 아닌 정수 n에 대해서 n!을 올바로 계산한다.

• n=0인 경우 : n=0인 경우 1을 반환한다. 올바르다.
• 임의의 양의 정수 k에 대해서 n<k 인 경우 n!을 올바르게 계산한다고 가정하자.
• n=k인 경우를 고려해보자. factorial은 먼저 factorial(k-1) 호출하는데 2번의 가정에 의해서 (k-1)!이 올바로 계산되어 반환된다. 따라서 메서드 factorial은 k*(k-1)! = k!을 반환한다.

x^n

x^0 = 1
x^n = x* x^n-1 if n>0

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 fubonacci (int n) {
	if(n<2)
    	return n;
    else
    	return fibonacci(n-1) + fibonacci(n-2);
}

 

최대공약수 : Euclid Method

ver 1.

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

=> m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n이고,
   그렇지 않으면 gcd(m,n) = gcd(n , m%n)이다.
   
  ver 2.
  
  public static int gcd(int p, int q) {
  	if(q==0)
    	return p;
    else
    	return gcd(q, p%q);
  }

 

순환적으로 사고하기

 

: 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.

 

문자열의 길이 계산 / 문자열을 프린트

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


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

 

문자열을 뒤집어 프린트

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

 

2진수로 변환하여 출력

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


=> 음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.
=> 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];
}

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

 

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

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

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

 

Recursion vs Iteration

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

순환 알고리즘의 설계

순환적 알고리즘 설계

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야함
• 모든 case는 결국 base case 로 수렴해야 함

=> 암시적 매개변수를 명시적 매개변수로 바꾸어라!

 

순차 탐색

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을 검색한다.
=> 즉, 검색구간의 시작점을 명시적으로 지정한다.
=> 이함수를 search(data, 0, n-1, target)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.

 

최대값 찾기

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

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);
    }
}