Functional Programming with Haskell - Recursion

함수 자신을 직접 또는 간접적으로 호출하는 함수를 재귀함수라고 한다. 

정수의 팩토리얼(N!) 을 계산하는 것이 전형적인 재귀의 예시이다. 

그럼 이를 하스켈로 작성해보자. 그리고 그 타입이 무엇인지 알아보자.

factorial n | n == 0 = 1
            | otherwise = n * factorial (n-1)

 
*Main> :load factorial
[1 of 1] Compiling Main ( factorial.hs, interpreted )
Ok, modules loaded: Main.
 
 
*Main> :type factorial
factorial :: (Eq a, Num a) => a -> a
 
 
*Main> factorial 40
815915283247897734345611269596115894272000000000
it :: (Eq a, Num a) => a
 

재귀 연산을 수동으로 추적하는 방법은 call 에 밑줄을 친 다음, 해당 call 을 textual expansion 을 가지고 다시 작성하는 것이다.

 
factorial 4
 
4 * factorial 3
 
4 * 3 * factorial 2
 
4 * 3 * 2 * factorial 1
 
4 * 3 * 2 * 1 * factorial 0
 
4 * 3 * 2 * 1 * 1
 
 

나머지가 1이 될 때까지 반복적으로 나누는 연산을 생각해보자.

 
*Main> 28 `quot` 3
9
it :: Integral a => a
 
*Main> it `quot` 3
3
it :: Integral a => a
 
*Main> it `quot` 3
1
it :: Integral a => a
 

나머지가 1이 될 때까지 몇 번 나눠야 하는지를 계산하는 재귀함수 numDivs 를 작성해보자.

numDivs divisor x | (x `quot` divisor) < 1 = 0
                  | otherwise = 1 + numDivs divisor (x `quot` divisor)

 
*Main> :load numdiv
[1 of 1] Compiling Main ( numdiv.hs, interpreted )
Ok, modules loaded: Main.
 
*Main> numDivs 3 28
3
it :: Num a1 => a1
 
*Main> numDivs 2 7
2
it :: Num a1 => a1
 

타입은 무엇인가?

 
*Main> :t numDivs
numDivs :: (Integral a, Num a1) => a -> a -> a1
 

그러면 numDivs 2 3.4 은 작동하는가?

*Main> numDivs 2 3.4
 
<interactive>:64:1:
    Could not deduce (Integral a0) arising from a use of ‘numDivs’
    from the context (Num a1)
      bound by the inferred type of it :: Num a1 => a1
      at <interactive>:64:1-13
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Integral Integer -- Defined in ‘GHC.Real’
      instance Integral Int -- Defined in ‘GHC.Real’
      instance Integral Word -- Defined in ‘GHC.Real’
    In the expression: numDivs 2 3.4
    In an equation for ‘it’: it = numDivs 2 3.4
 
<interactive>:64:9:
    Could not deduce (Num a0) arising from the literal ‘2’
    from the context (Num a1)
      bound by the inferred type of it :: Num a1 => a1
      at <interactive>:64:1-13
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Integral a => Num (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      instance Num Integer -- Defined in ‘GHC.Num’
      instance Num Double -- Defined in ‘GHC.Float’
      ...plus three others
    In the first argument of ‘numDivs’, namely ‘2’
    In the expression: numDivs 2 3.4
    In an equation for ‘it’: it = numDivs 2 3.4
 
<interactive>:64:11:
    Could not deduce (Fractional a0) arising from the literal ‘3.4’
    from the context (Num a1)
      bound by the inferred type of it :: Num a1 => a1
      at <interactive>:64:1-13
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Integral a => Fractional (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      instance Fractional Double -- Defined in ‘GHC.Float’
      instance Fractional Float -- Defined in ‘GHC.Float’
    In the second argument of ‘numDivs’, namely ‘3.4’
    In the expression: numDivs 2 3.4
    In an equation for ‘it’: it = numDivs 2 3.4
*Main>
 

아래와 같이 2개의 어플리케이션에 식별자를 붙여보자. 

 
*Main> let f = numDivs 2
f :: (Integral a, Num a1) => a -> a1
 
*Main> let g = numDivs 10
g :: (Integral a, Num a1) => a -> a1
 
*Main> f 9
3
it :: Num a1 => a1
 
*Main> g 1001
3
it :: Num a1 => a1
 

f 나 g 보다 좀 더 직관적인 이름으로 바꿔보자. 

 
*Main> let floor_log2 = numDivs 2
floor_log2 :: (Integral a, Num a1) => a -> a1
 
*Main> floor_log2 1000
9
it :: Num a1 => a1
 
*Main> let floor_log10 = numDivs 10
floor_log10 :: (Integral a, Num a1) => a -> a1
 
*Main> floor_log10 1000
3
it :: Num a1 => a1