엄범


효율을 위해 memoization과 함께 사용하면 좋다.

[Languages & Frameworks/JS] - [JS] memoization, currying


재귀 호출은 어떤 문제가 유사한 하위 문제로 나뉘어지며 각각의 문제를 같은 해결 방법으로 처리할 수 있을 때 사용할 수 있다.

일반적으로 하위 문제를 처리하기 위해 자기자신을 호출한다.

```

전체 - Level 1 - Level 2 - ... - Level n

```


위와 같은 경우 call stack은 이런 식이다.

 ...

 Level2

 Level1

 전체 


주의할 점은 recursive function 내에서 자기 자신을 호출하는 것이 두 번 이상일 경우 각 작업 단위가 순차적으로 증가하지는 않는다는 점이다.

예를 들어 다음과 같이 Level n까지 내려갔다가 다시 Level n-1이 되었다가, 또 다시 Level n이 되는 등 단순히 증가하거나 감소하지 않는다.

```

전체 - Level 1 하위.1 - Level 2 하위.1 - ... Level n-1 하위.1 - Level n - Level n-1 하위.2 - Level n - ....

```

그래서 수열같이 단순히 이전 작업 수행의 결과를 나열해서 규칙을 찾으려면 잘 안보인다.


recursive function 내에서 자기 자신을 한 번만 호출하는 경우

``c return recursive_function()`` 같이 재귀 호출 값을 반환하는 방식으로 많이 사용하며 이를 꼬리 재귀(tail recursion)라고 부른다.


recursive function 내에서 자기 자신을 두 번 호출하는 경우

하노이의 탑 같은 경우.




'Algorithm > Theory' 카테고리의 다른 글

점근적 표기 / 평균 수행 시간 분석  (0) 2018.04.20
피보나치 수  (0) 2018.04.20
Quicksort  (0) 2018.04.08
Primality test  (0) 2017.11.19
재귀, recursion  (0) 2017.05.31
P, NP, NP-hard, NP-complete  (0) 2016.08.15