재귀, recursion

효율을 위해 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 내에서 자기 자신을 한 번만 호출하는 경우

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

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

• 하노이의 탑 같은 경우.
• 또는 아래와 같은 경우.

>>> def f(x):
   ...     if (x == 0):
   ...         return 1
   ...     return f(x-1) + f(x-1)

• 피보나치 같은 경우 n-1, n-2라 최하위 depth가 진행 할 수록 달라진다.

fun f(n):
if (n <= 2) return 1
return f(n-1) + f(n-2)