1-3강 - Algorithm specification (2) 재귀 알고리즘

4. Recursive Algorithm

1) 기본

1> if-else 구문이나 while문을 사용하는 함수는 recursive하게 구현할 수 있다.

2> 자기 식 안에 자기 자신이 있는 것을 발견하면 된다.

3> 계산하는데 엄청난 시간이 걸릴 수 있다.

 

2) 분류

1> Direct recursion: 함수 내에서 함수 본인을 다시 호출하는 것

2> Indirect recursion: 자신을 호출한 함수를 다시 호출하는 것

 

3) 중요 point 2가지

1> 재귀 호출을 중단할 조건을 만든다.

2> recursive 호출을 통해 점점 원하는 결과와 가까워져야 한다.

 

4) 예시

자기 식 안에 자기 자신이 있는 것을 발견하면 된다.

1> combination

- iterative 관점에서는 1~n의 수를 곱하는 것이지만

- recursive 관점에서는 (n-1)!에 n을 곱하는 것

- 'nCk'은 내부에 'n-1Ck-1'과 'n-1Ck'이라는 자기 자신이 있다는 것을 발견하기

=> combination 식 안에 combination이 있다.

2> factorial 

- 'n!'은 내부에 (n-1)!'이라는 자기 자신이 있다는 것을 발견하기

3> binary search

- binarySearch를 하고나서 middle과 searchNum이 다르면 다시 줄어든 범위에서 binarySearch를 진행한다.

 

 

5) fibonacci

 

 

 

 

 

최종: 재귀를 사용해야 할 때 내가 할 것 (순서)

1) 재귀적으로 식을 구성하기

2) 중단조건 만들기