[Algorithm] 순환 ①

- 순환 (recursion) : 자기 자신을 호출하는 함수. 재귀함수.

=> 무한루프에 빠지는 경우가 있음.

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

    ② Recursive case : recursion을 반복하다보면 결국 Base case로 수렴해야 함.

    위 2가지 요구사항을 충족하면 무한루프에 빠지지 않음.

 

순환함수는 수학적귀납법으로 증명 가능함.

 

Ex) Factorial : n! 을 순환함수로 만들어보자

     public static int factorial ( int n ) {

              if ( n == 0 ) 

                  return 1 ;

              else

                  return n * factorial ( n - 1 ) ; }

=> 수학적귀납법 증명 

1. n = 0인 경우에 1을 반환하며 이는 올바름.

2. 임의의 양의 정수 k에 대해서 n < k인 경우 n!을 올바르게 계산한다고 가정함.

3. n = k인 경우를 고려해봄. factorial은 먼저 factorial ( k - 1 )을 호출하는데 2번의 가정에 의해

   ( k - 1 )!이 올바르게 계산되어 반환됨. 즉, 메서드 factorial은 k * ( k - 1 )! = k!을 반환함.

 

+) X^n 구하기 & Fibonacci 수열 구하기 & 최대공약수 구하기