Recursion

Recursion

 

자기 자신을 호출하는 함수.  순환, 재귀

recursion이 항상 무한루프에 빠지는 것이아니다.

 

 

무한루프에 빠지지 않는 적절한 구조

 

Base case :  적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

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

 

 

수학적귀납법과의 비교

 

Ex)

1. 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까지의 합을 올바로 계산하여 반환한다.

n!, x^n, finonacci number(f0=0, f1=1, fn = fn-1 + fn-2, n>1), 최대공약수(Euclid Method)

 

public static int gcd(int p, int q){

     if(q==0)

        return p;

     else

       return gcd(q, p%q);

}

 

 

Recursive Thinking

 

문자열의 길이 계산

 

public static int length(String str){

    if(str.equals(“”))

        return 0;

    else

        return 1+length(str.substring(1));

}

 

 

배열의 합구하기

 

public static int sum(int n, int[] data){

     if(n<=0)

        return 0;

     else

        return sum(n-1, data) + data[n-1];

}

 

 

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

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

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

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

 

 

순환적 알고리즘 설계

 

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

예를 들어 순차탐색 시, 매개변수에 begin과 end로 표기. 그리고 return search(data, begin+1, end, target)

 

 

상태공간트리

 

상태공간트리란 찾는 해를 포함하는 트리.

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함

따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님.

 

 

 Powerset 

 멱집합