귀속 입문

이 기사를 통해서 알게 된 것들.

귀속함수

귀속 함수의 처리 순서

비망록 귀속

이른바 회귀

프로그램에서 자신을 호출하는 것을 귀속 호출이라고 하고, 귀속 호출을 하는 함수를 귀속 함수라고 한다.
케이스

int func(int n) {
  func(n - 1);
}

이상은func 함수를 무한 호출하는 함수입니다.func 함수에서 자신을 호출합니다.이것은 귀속 함수다.단, 이렇게 하면 처리가 끝나지 않기 때문에 처리 내에서 처리를 끝내는 조건을 정의해야 한다.
그렇다면 이 내용을 수정하고 무한 회귀하지 말자.

int func(int n) {
  if (n == 0) return 0;
  return func(n - 1);
}

// func関数の呼び出し
func(10);
// => 0

이렇게 하면func 함수의 귀속을 무한히 호출하는 것을 방지할 수 있다.
만약 단지 이렇다면 아무것도 계산하지 않을 것이다. 그래서 수정을 더하면 1에서 N의 총계를 구하는 함수가 된다.

int func(int n) {
　　if (n == 0) return 0;
　　return func(n - 1) + n; // + nを追加
}

// func関数の呼び出し
func(10);
// => 55

집행 결과를 보면 1 - 10의 총계를 구할 수 있다.
왜 이런 결과가 나왔을까, 처리 순서를 추적해보자.

0. func(10)を実行する

1. func(10 - 1)が呼び出される
  => func(9)が実行される

2. func(9 - 1)が呼び出される
  => func(8)が実行される

3. func(8 - 1)が呼び出される
  => func(7)が実行される

4. func(7 - 1)が呼び出される
  => func(6)が実行される

5. func(6 - 1)が呼び出される
  => func(5)が実行される

6. func(5 - 1)が呼び出される
  => func(4)が実行される

7. func(4 - 1)が呼び出される
  => func(3)が実行される

8. func(3 - 1)が呼び出される
  => func(2)が実行される

9. func(2 - 1)が呼び出される
  => func(1)が実行される

10. func(1 - 1)が呼び出される
  => func(0)が実行される
  => ここで初めて再帰呼び出しが終了する。　
  => ０が返却される

11. No.9で実行されたfunc(1)の計算が行われる
  => 1 + 0 // 0はfunc(0)の結果
  => 1が返却される

12. No.8で実行されたfunc(2)の計算が行われる
  => 2 + 1 // 1はfunc(1)の結果
  => 3が返却される

13. No.7で実行されたfunc(3)の計算が行われる
  => 3 + 3 // 3はfunc(2)の結果
  => 6が返却される
 
14. No.6で実行されたfunc(4)の計算が行われる
  => 4 + 6 // 6はfunc(3)の結果
  => 10が返却される

15. No.5で実行されたfunc(5)の計算が行われる
  => 5 + 10 // 10はfunc(4)の結果
  => 15が返却される

16. No.4で実行されたfunc(6)の計算が行われる
  => 6 + 15 // 15はfunc(5)の結果
  => 21が返却される

17. No.3で実行されたfunc(7)の計算が行われる
  => 7 + 21 // 21はfunc(6)の結果
  => 28が返却される
 
18. No.2で実行されたfunc(8)の計算が行われる
  => 8 + 28 // 28はfunc(7)の結果
  => 36が返却される

19. No.1で実行されたfunc(9)の計算が行われる
  => 9 + 36 // 36はfunc(8)の結果
  => 45が返却される

20. 最初に実行したfunc(10)の計算が行われる
  => 10 + 45 // 45はfunc(9)の結果
  => 55が返却される
  => func(10)の処理結果は55となる。

귀속 함수 중의 피보나치 수열

피보나치 수열
1123 5813 213455
이것을 다시 설치하면 다음과 같다.

class Fibonacci {
  static long calculate(int n) {
    if (n == 1 || n == 2) return 1;

    return calculate(n - 1) + calculate(n - 2);
  }

  public static void main(String[] args) {
    for(int n = 1; n < 10; n++) {
      System.out.println(n + ": " + calculate(n));
    }
  }
}

처리 결과

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

필기화 귀속

필기화 회귀

수조 등에서 함수 호출 결과를 유지하고 매번 함수 호출이 다시 계산되는 것을 방지하는 방법.
상기 피보나치 수열의 처리를 필기화 회귀를 이용하여 처리 효율을 높인다.

class Fibonacci {
  // nの最大を999とする
  static long[] memo = new long[1000];

  static long calculate(int n) {
    if (n == 1 || n == 2) return 1;

    if (memo[n] != 0) {
      return memo[n];
    } else {
      long result = calculate(n - 1) + calculate(n - 2);
      memo[n] = result;
      return result;
    }
  }

  public static void main(String[] args) {
    for(int n = 1; n < 10; n++) {
      System.out.println(n + ": " + calculate(n));
    }
  }
}

매개 변수 n에 대한 계산 처리를 피하고 중복 처리를 생략하기 위해 수조에 값을 저장한다.
실제 손 옆에서 동작을 확인하고 처리 속도가 얼마나 변했는지 확인하세요.
필기화 컴백의 경우 n=50도 곧 끝나야 한다.반면 노트화로 복귀하지 않으면 시간이 많이 걸린다.
이상은 컴백 입문.
자신의 이해를 깊게 하기 위해 쓴 기사가 다른 사람에게 도움이 된다면 정말 좋겠다.
잘못된 점이 있으면 메시지를 남겨 주세요.