재귀함수란?
- 자기 자신을 호출하는 함수
- 예를 들어,
"상호"가 "상호"에게 "'상호'야! 5 곱하기 3 한 결과 값을 반환해줘!" 와 같다.
우스꽝스러운 예문이긴 하지만 직관적으로 이해하기 위해 위와 같은 예제를 만들었다.
- 재귀함수는 항상 다음 2 가지로 구성된다.
1) base case
2) recursive case
추가설명:
1) base case 의 경우 함수가 끝나는 case(i.e. 지점)을 정의하는 것이다.
2) recursive case 의 경우 반복적으로 수행할 연산을 정의하는 것이다.
대부분의 사람들이 관심있는 부분은, 어떻게 재귀함수를 쉽게 정의하는가 이다.
보통 다음 순서로 접근하는 것이 효율적이라고 본다.
1) 연산이 수행되는 과정을 나열한다. (i.e. 패턴을 찾는다)
2) base case 를 정한다.
3) recursive case 를 정한다.
재귀함수라고 하면, 겁부터 나기 쉽상이다.
천재가 아닌 이상 머릿속으로 그리는 것이 당장 쉽지 않기 때문이다.
대부분의 경우, 좌절해버리기 마련이지만 침착하게 위의 일련의 과정을 거쳐서 결론에 도달하면 된다.
재귀함수 예문
e.g.
factorial 함수
# let rec fact n =
1
else
n * fact(n-1)
;;
val fact : int -> int = <fun>
# fact 3;;
- : int = 6
fibonacci 함수
# let rec fibonacci n =
if n < 2 then
1
else
fibonacci(n-1) + fibonacci(n-2)
;;
val fibonacci : int -> int = <fun>
# fibonacci(5);;
- : int = 8
위 fibonacci 함수를 'pattern matching' 을 이용하여 다음과 같이 정의할 수도 있다!
# let rec fibonacci x =
match x with
0 -> 1
| 1 -> 1
| _ -> fibonacci (x-1) + fibonacci (x-2)
;;
val fibonacci : int -> int = <fun>
# fibonacci 5;;
- : int = 8
WRITTEN BY
