[알고리즘] 순환(Recursion)의 개념과 기본 예제 1, 2, 3

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

java식) 자기 자신을 호출하는 method

> void func(...)
	{
    		...
        	func(...);
        	...
   	 }

what will happen?

public class Code01 {
	public static void main(String [] args) {
    	func();
       }
public static void func() {
	System.out.println("Hello");
    func(); #자기자신을 다시 호출
    }
   }

무한루프에 빠짐

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

 

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

return하면 control이 항상 자기 자신을 호출했던 다음 문장으로 넘어가는데 func(k-1)로 이동 func(0)가 호출되었다가 아무일도 일어나지 않고 종료되었으니까

이 다음 문장을 실행해야하는데 func(k-1) 다음엔 아무 문장이 없기 때문에 다시 호출된 함수 func(k-2)로 넘어가는데 역시 종료 되고 또 종료되어서

마지막으로 func(n)까지 return이 되어서 func(n)이 종료

적절한 구조를 가지고 있다면 무조건 recursion이라고 무한 루프에 빠지는 게 아니다.

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

public class Code02 {
	public static void main(String [] args) {
    int n = 4; 
    func(n); 
    //Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다.
  }
  
    public static void func(int k) {
    	if(k<=0)
        	return;
        else {
        	System.out.println("Hello");
            func(k-1);
            // Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
        }
      }
    }

 

 

 

순환적으로 사고하기

프로그램이라는 것을 보는 하나의 관점이 순환 안에 내재되어 있다고 볼 수 있다.

 

순환은 수학 함수 계산에만 유용할까?

수학 함수 뿐 아니라 다른 많은 문제들을 순환으로 해결할 수 있다. 예를 들어 문자열의 길이 계산 문제가 있다고하자. for 문이나 while문을 이용하여 구할 수도 있지만, 원래 문자열에서 첫 번째 문자를 제거한 후 남은 나머지 문자열의 길이에 +1 하면 된다는 순환적인 알고리즘을 생각해낼 수 있다. -문자열 길이 계산에서의 순환 활용

 

 

 

substring() 메서드 ? 원래 문자열에서 맨 앞의 문자를 제거한 문자열을 만들어주는 메서드

 

문자열을 뒤집어 프린트

 

2진수로 변환하여 출력

 

배열의 합

 

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

 

 

 

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

 

순환적인 알고리즘 설계

 

적어도 하나의 Base Case, 순환되지 않고 종료되는 Case가 있어야한다. 모든 Case는 결국 Base Case로 수렴한다. 경우에 따라서는 Base Case가 여러 개일 경우도 있다.

 

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

 

순차탐색

 

int Search(int[] data, int n, int target) {

for(int i = 0 ; i <n; i++)} ---

 

매개변수의 명시화: 순차 탐색 - 이 함수의 미션은 data[begin]에서 data[end] 사이에서 Target을 검색한다. 즉, 검색 구간의 시작점을 명시적으로 지정한다. 일반적으로 순환의 형태를 가지는 함수의 경우 매개변수 설정에서 고려해야할 점이 있다. 외부에서 함수가 호출되었을 때만을 생각하는 것이 아니라 자기자신을 호출했을 경우 전달될 매개변수를 고려해야한다. 그렇기에 검색할 부분의 시작위치를 지정해주는 것이 중요하다(매개변수의 명시화) 물론 생략하는 경우도 있음! 어찌되었든 순환 함수를 만들 때는 매개변수의 명시화가 중요하다는 것을 기억하자.

 

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

이진탐색 알고리즘에서 순환이용하기

이진탐색 알고리즘은 본질 자체가 순환적이다.