Recursive Function
Recursive라는 표현은 아마 모든 분들이 익숙하실 겁니다. (한국어로 재귀라고 합니다) 간단히 설명드려 함수를 다루는 기법하나로 함수 내부에서 그 함수를 다시 호출하는 것을 말하는데요. Functional Programming에서 가장 중요하게 생각하는 것이 여기서 tail call을 없애는 겁니다. Stack이 쌓이는 경우 때문인데, 다음 설명을 계속 보겠습니다.
factorial :: Int -> Int
factorial n = product [1..n]
위의 예제는 간단히 factorial을 product를 이용하여 구현한 것 입니다. 이 함수를 이용할 경우 다음의 과정을 거치게 될 것입니다.
factorial 4
= product [1..4]
= product [1,2,3,4]
= 1*2*3*4
= 24
다음은 이 함수를 Recusive하게 구현한 것입니다.
factorial 0 = 1
factorial n = n * factorial (n-1)
아마 이런 구현은 알고리즘 과목의 첫 예제 정도로 많이 나옵니다. 0일 경우 1로 하여 기저를 정의하고, 점차 n-1을 다시 호출함으로써 결과를 받아 곱하게 됩니다. 물론 이렇게 구현하였지만 위의 list를 이용한 구현과 굉장히 유사하게 동작하는 것을 확인할 수 있습니다.
factorial 3
= 3 * factorial 2
= 3 * (2 * factorial 1)
= 3 * (2 * (1 * factorial 0))
= 3 * (2 * (1 * 1))
= 3 * (2 * 1)
= 3 * 2
= 6
위의 예를 보면 stack에 factorial 0의 경우까지 쌓여있다 점차적으로 계산 결과를 얻어오는 방향으로 진행되게 됩니다.
(프로그램 메모리에서 stack의 동작이 어떻게 돌아가는지 이해가 안되신다면 어려울 수 있습니다. 간단히 지역변수와 리턴 address가 저장되는 공간으로, 여기서 이전 함수가 종료되지 않는 가운데 계속해서 새로운 공간을 할당하게 됩니다. 따라서, stack이 쌓이는 결과를 볼 수 있습니다.)
물론 여기서 n이 0보다 작을 경우 무한히 돌 수 있다는 문제도 있네요...
그럼 왜 Recursive function을 사용하는 걸까요? 물론 위의 예의 경우 list의 경우가 더 이해하기 쉬우나, Recursive function은 많은 부분을 추상화(abstract)하기 때문에 간단하며 이해하기 쉽기 때문입니다.
Recursion on Lists
Recursive function 은 어렵지 않게 list에 대해서도 구현이 가능합니다.
product :: [Int] -> Int
product [] = 1
product (n:ns) = n * product ns
위의 코드는 list (n:ns)에 대해 구현된 product 함수입니다. 어렵지 않게 이해할 수 있으며, list의 tail인 ns에 대해 재귀로 동작하는 것을 볼 수 있습니다.
product [2,3,4]
= 2 * product [3,4]
= 2 * (3 * product [4])
= 2 * (3 * (4 * product []))
= 2 * (3 * (4 * 1))
= 2 * (3 * 4)
= 2 * 12
= 24
위 예를 통해 factorial 과 동작이 동일하다는 것을 알 수 있습니다. 다른 함수를 더 보겠습니다.
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
length와 reverse 의 경우에도 동일하게 재귀로 구현된 것을 확인 할 수 있습니다. (동작은 보지 않겠습니다.)
Multiple Arguments
여러 매개변수를 가지고 recursive function을 구현 할 수 있습니다. 다음 예를 통해 설명하겠습니다.
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
이전 포스팅에서 다뤘던 zip 함수의 경우도 내부에서 재귀적으로 동일 함수를 호출 하는 것을 볼 수 있습니다. 몇가지 예를 더 보겠습니다.
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
(이해가 어렵더라도 동작하는 과정을 상상하면 어렵지 않게 이해할 수 있을 겁니다.)
Quicksort
Quicksort 는 다양한 알고리즘 서적에 단골 처럼 나오는 정렬 기법 중 하나 입니다. (잘 모르시는 분의 경우 Quicksort Algorithm을 참조하시기 바랍니다.) 속도가 빠른 것으로 알려져 많은 언어에서 정렬이 필요할 경우 이를 이용합니다. 이런 Quicksort 를 Haskell에서 어떻게 구현하는지 알아봅시다.
Quicksort는 다음 두가지 조건을 따릅니다.
- 비어있는 list는 이미 정렬이 된 상태로 봅니다.
- 비어있지 않은 list의 경우, head를 중심으로 tail의 값을 탐색하며 head보다 작거나 같은 값은 앞으로, head보다 큰 값은 뒤로 붙여 list를 만듭니다.
이러한 조건에 따라 Quicksort를 구현하면 다음과 같습니다.
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) =
qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]
위를 보면 정말 짧으면서도 이해하기 쉽습니다. 물론 동작이 과연 어떻게 될지도 다음 예를 보면 이해할 수 있습니다.
qsort [3,2,4,1,5]
= qsort [2,1] ++ [3] ++ qsort [4,5]
= (qsort [1] ++ [2] ++ qsort []) ++ [3] ++
(qsort [] ++ [4] ++ qsort[5])
= ([1] ++ [2] ++ []) ++ [3] ++ ([] ++ [4] ++ [5])
= [1,2,3,4,5]
Quicksort 이외에 recursive function을 이용하여 구현된 함수들을 보겠습니다.
replicate :: Int -> a -> [a]
(!!) :: [a] -> Int -> a
elem :: Eq a => a -> [a] -> Bool
간략하게 설명하자면, 위의 함수들은 모두 하나의 list에 대해 재귀적으로 접근하여 값을 얻어오거나 list를 만들 수 있습니다. (상상해보시기 바랍니다. 실제로 구현해보는 것도 좋을 것 같습니다. 물론 filter, list comprehension 등을 이용하여 구현할 수 있습니다.)