Haskell - 递归

你好，递归

递归是指在定义的应用自身的方式，将白了就是函数会自己调用自己。“从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲的是什么呢：从前有座山，山里有座庙……”
数学定义中存在的递归随处可见，比如斐波那契数列，杨辉三角形等。递归在函数式语言中能够发挥真正的威力，因为在函数式编程中，重要的不是给出求解的步骤，而是定义问题与解的描述。
在下文会使用Haskell和C++两种语言进行描述。

1. 求列表中元素的最大值

   maximumNumber :: (Ord a) => [a] -> a
   maximumNumber [] = error "maximumNumber of empty list"
   maximumNumber [oneElement] = oneElement
   maximumNumber (element : elements) = max element (maximumNumber elements)
   
   main = do
       print $ maximumNumber [1, 4, 2, 3, 5, 6, 7, 8, 9, 10]

2. 求斐波那契数列

   fibonacci :: (Num a, Ord a) => a -> a
   fibonacci 0 = 0
   fibonacci 1 = 1
   fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

template<size_t N> constexpr size_t fibonacci = fibonacci<N-1> + fibonacci<N-2>;
template<> constexpr size_t fibonacci<1> = 1;
template<> constexpr size_t fibonacci<0> = 0;

3. 实现replicate

   replicate' :: Int -> a -> [a]
   repllicte' n x
   	| n <= 0 = []
   	| otherwise = x:replicate' (n-1) x

4. 实现take

   take' :: (Num i, Ord i) => i -> [a] -> a
   take' n _        
   	| n <= 0     = []
   take' _ []       = []
   take' n (x:xs)   = x : take' (n-1) xs