[Algorithm] Recursive Function

의미란? 귀납적 계산 방법 (귀납적 문제해결 방법)

크게 두 가지 계산 방법이 있음.

1. 순차적 

2. 귀납적

◈ 순차적 계산법

예를 들면, 4의 약수의 개수를 구하여라.

1로 나누어지면 c++;

2로 나누어지면 c++;

....

스텝별로 하는 것을 의미한다. 

즉, 반복문을 통한 계산이 의미하는 것이 첫 번째 계산법이다.

◈ 귀납적 계산법

팩토리얼을 구하기 위해서 팩토리얼을 쓴다.

귀납적으로 정의된 밑의 식이 참된 정의이다.

f(5) = 5 x f(4) = 5 x 4 x f(3) .... = 5 x 4 x 3 x 2 x 1 x f(0)

귀납적으로 정의해야 하는 것들은 반드시 멈추어야 하는 지시가 있어야 한다.

0! = 1 (정의)

n ! 은 n x (n-1)! , 0! = 1 이라는 정의가 필요하다. 

"나" 를 계산하기 위해 또 다시 "나"를 활용한다.

n^m 을 귀납적으로 정의하면 다음과 같다.

5^4을 구한다고 가정하자.

5를 네 번 곱한 값이 제대로 나올려면 '5^3이 5를 세 번 곱한 값이다' 라는 가정이 필요하다.

즉, 5의 4승이 5를 네 번 곱한 값이 나올려면 5의 3승은 5를 세 번 곱한 값이다라는 가정이 성립을 해야 한다.

5의 3승이 5를 세 번 곱한다면 한 번 더 5를 곱하여 5의 4승을 만들 수 있다.

5의 3승은 5의 2승 곱하기 5이다 -> 5의 2승은 5를 두 번 곱하다라는 가정으로 맞추어 짐.

5의 1승이 정말로 5를 한 번 곱할까? ... 여기서 함수의 관계가 제대로 나오게 된다. 

여기서 팩토리얼에서 보았던 재귀 호출의 흐름이 반복되는 것을 알 수 있다.

 

5의 1승은 5^0 x 5... '5의 0승은 1이다' 라고 정의가 되어 있음. (약속)

즉, 수 많은 가정을 하다가.... 마지막에는 우리가 직접 정의한 정확한 값이 있기 때문이다.

         return 으로 자기를 호출하고,,,,                  if로 정의하기