2. Recursion(1)

인프런의 '영리한 프로그래밍을 위한 알고리즘 강좌' 내용 정리입니다.

        Recursion이란?

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

pubilc class Code01 {
	public static void main(String [] args) {
    	func();
    }
    
    public static void func() {
    	System.out.println("Hello...");
        func();// 재귀 함수
    }
}

• 무한 루프에 빠지지 않는 재귀 함수
  적어도 하나의 recursion에 빠지지 않는 경우를 만들면 된다.

pubilc class Code01 {
	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);// 재귀 함수
        }
    }
}

• 다양한 예를 구현할 수 있다.
  n부터 1 까지의 합 : n + func(n-1)
  n! : n * func(n-1)
  xⁿ : x * power(n-1)
  피보나치 : fibonacci(n-1) + fibonacci(n-2)
  최대 공약수 (유클리드 메서드) : if(q == 0) return p; else gcd(q, p%q);
• 수학적 귀납법을 통해 증명하는게 좋다.

---

• 문자열의 길이 계산

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.print(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);
    }
}

• 배열의 합 구하기

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

---

        Recursion vs Iteration

• 모든 순환 함수는 반복문(iteration)으로 변경 가능하다.
• 그 역도 성립한다.
• 복잡한 알고리즘을 단순하게 만들어줌
• 함수 호출에 따른 오버헤드를 주의할 것.