【算法】递归应用_常见算法的递归实现

前面学习了递归，趁热打铁就把常见的一些算法用递归实现了一遍，找找递归的感觉。斐波那契数列用递归函数定义如下：(1) n = 0时，f(n) = 0(2) n = 1时，f(n) = 1(3) n > 1时，f(n) = f(n-1) + f(n-2)–Haskellfibonacci :: (Num a, Eq a) => a -> afibonacci 0 = 0fibonacci 1 = 1fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)这代码几乎就是上面的递归定义原封不动的“照搬”。当然这个版本性能并不是太高，优化的空间很大，这里不讨论。插入排序大部分人在打牌的时候无意中就使用了这个算法。左手拿着排序好的排【一开始没有牌，当然满足条件】，假设按升序排列，每次右手摸完牌都会插入到左手适当的位置来保持左手中的牌是有序的。人的话，可能并没有意识到，实际上你在插入牌的时候，是通过将右手的牌或者从头开始或从尾开始依次跟左手的牌对比，然后找到合适的位置。时间复杂度为O(n2)。我们可以递归定义如下：（1）如果列表内没有元素，我们就返回空列表（2）如果列表不为空，对列表元素的排序，可以认为就是将列表首元素插入到已经排好序的其他元素中，这些元素的排序通过插入排序实现。代码如下：–HaskellinsertionSort :: Ord a => [a] -> [a]insertionSort [] = []insertionSort (x:xs) = insert x $ insertionSort xsinsert :: Ord a => a -> [a] -> [a]insert x y = let (p,q) = span (<x) y in p ++ [x] ++ q冒泡排序这个算法也较为直观，假设升序排列，第一次遍历会将最大的元素移动到列表的右侧，怎么移动的呢？只要从左到右，依次比较当前位置的元素和右侧的元素，交换顺序不对的两个元素的位置。通过多次遍历，最终得到所有元素有序的列表。时间复杂度为O(n2)。–HaskellbubbleSort :: Ord a => [a] -> [a]bubbleSort [] = []bubbleSort x = bubbleSort initx ++ [lastx] where x’ = swap’ x initx = init x’ lastx = last x’swap’ :: Ord a => [a] -> [a]swap’ [] = []swap’ [x] = [x]swap’ (x1:x2:xs) | x1 > x2 = x2 : swap’ (x1 : xs) | otherwise = x1 : swap’ (x2 : xs)归并排序这个算法的效率较高，时间复杂度为O(nlogn)，采用了分治思想，即：将元素分为两部分，每一部分分别采用归并排序算法排序，然后将这两部分已排序的部分合并为整体有序。–HaskellmergeSort :: Ord a => [a] -> [a]mergeSort [] = []mergeSort [x] = [x]mergeSort xs = merge (mergeSort x1) (mergeSort x2) where (x1, x2) = splitAt half xs half = (length xs) div 2merge :: Ord a => [a] -> [a] -> [a]merge [] ys = ysmerge xs [] = xsmerge x1@(x:xs) y1@(y:ys) | x > y = y : merge x1 ys | otherwise = x : merge xs y1二分算法在前面实现了一版，如下–Haskellimport qualified Data.Vector as VbinarySearch :: (Ord a)=> V.Vector a -> Int -> Int -> a -> Maybe IntbinarySearch vec low high e | low > high = Nothing | vec V.! mid < e = binarySearch vec (mid+1) high e | vec V.! mid > e = binarySearch vec low (mid-1) e | otherwise = Just mid where mid = low + ((high-low) div 2)但只能返回一个元素，如果我们想返回所有与e相等的元素位置该怎么办呢？一种非递归的方案可能是：使用上面得到的位置，然后使用循环向前和向后搜索，从而得到与之相等的所有元素的索引。下面是递归的版本，与循环版本对应，只不过在找到相等元素的时候继续往下递归即可。–Haskellimport qualified Data.Vector as VbinarySearch’ :: (Ord a) => V.Vector a -> Int -> Int -> a -> [Int]binarySearch’ vec low high e | low > high = [] | vec V.! mid < e = binarySearch’ vec (mid + 1) high e | vec V.! mid > e = binarySearch’ vec low (mid - 1) e | otherwise = binarySearch’ vec low (mid - 1) e ++ [mid] ++ (binarySearch’ vec (mid + 1) high e) where mid = low + ((high - low) div 2)下一章介绍的快速排序也是递归的范本，下一篇文章介绍。微信公众号