[Recursion] 개념

Recursion

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

 

What is Recursion

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

 

예제 Code01.java

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

실행 결과 무한 루프에 빠지게 된다.

Recursion은 항상 무한루프에 빠질까?

• No! 항상 그렇지 않다.

 

예제 Code02.java

public class Code02{
  public static void main(String[] args){
    int n = 4;
    func(n);
  }
 
  public static void func(int k){
    // 종료 조건 
    if (k<=0){
      // return 문을 만나면 함수를 호출한 곳으로 돌아간다. 
      return;
    }else{
      System.out.printle("Hello world");
      // 재 호출 시 k 값을 -1 
      func(k-1);
    }
  }
}

1. 종료 조건을 넣어 준다.
2. 재 호출시 매개변수의 값을 1감소 시켜준다.

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

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

Code02.java 에서 func(k-1)을 func(k)로 변경한다면 결국 무한루프에 빠지게 된다.

recursion이 무한 루프에 빠지지 않기 위한 기본 요구 사항 2가지. 

반드시 지켜줘야 한다.

 

1~n까지의 합

예제 Code03.java

func(int n) 

1~n 까지의 합

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

수행 단계

1. int result = func(4);
2. func(4) = return 4 + func(3);
3. func(3) = return 3 + func(2);
4. func(2) = return 2 + func(1);
5. func(1) = return 1 + func(0);
6. func(0) = return 0;

4 + 3 + 2 + 1 + 0 의 결과를 나타낸다. 결과는 10. 1부터 4까지의 합.

recursion의 해석

• 약간의 요령이 필요하다.
• 일반적인 코드를 이해하는 방법과는 다른 방법으로 해석해야 한다.
• 수학적귀납법으로 해석한다

 

Code03.java의 수학적귀납법

1. n=0인 경우 : n=0인 경우 0을 반환한다. 올바르다.
2. 임의의 양의 정수 k에 대하여 n<k인 경우에 0에서 n까지의 합을 올바르게 계산한다고 자정한다.
3. n=k인 경우 : func는 먼저 func(k-1)을 호출하는데 2번의 가정에 의하여 0~k-1까지의 합이 올바르게 계산되어 반환된다.
   메서드 func는 그 값(func(k-1))에서 n을 더하여 반환단다.
   따라서 func는 0에서 k까지의 합을 올바르게 계산하여 반환한다.

 

출처

https://www.youtube.com/watch?v=ln7AfppN7mY&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=1