def foo():
 foo()

foo()

def foo(n):
 if n <= 1:
 return
 foo(n-1)

foo(10)

# 不要用这个函数，还是用原生的 max 吧。
def max2(list):
 if len(list) == 1:
  return list[0]
 head, tail = list[0], list[1:]
 return head if head > max2(tail) else max2(tail)

print max2([3,98,345])
# 345

const max = xs => {
 if (xs.length === 1) return xs[0];
 const [head, ...tail] = xs;
 return head > max(tail) "htmlcode">

# Python 内置有 reverse 函数
def reverse2(list):
 if len(list) == 1:
 return list
 head, tail = list[0], list[1:]
 return reverse2(tail) + [x]

print reverse2([1,2,3,4,5,6])
# [6,5,4,3,2,1]


JS 版：




const reverse = xs => {
 if (xs.length === 1) return xs;
 const [head, ...tail] = xs;
 return reverse(tail).concat(head);
};


map


Python 版：




# Python 内置有 map 函数
def map2(f, list):
 if len(list) == 0:
 return []
 head, tail = list[0], list[1:]
 return [f(head)] + map2(f, tail)

print map2(lambda x : x + 1, [2,2,2,2])
# [3,3,3,3]


JS 版：




const map = f => xs => {
 if (xs.length === 0) return [];
 const [head, ...tail] = xs;
 return [f(head), ...map(f)(tail)];
};


zipWith


zipWith 接受一个回调函数和两个列表为参数。他会并行遍历两个列表，并把单遍历到的元素一一对应，传进回调函数，把每一步遍历的计算结果存在新的列表里，最终返回这个心列表。


Python 版：




def zipWith(f, listA, listB):
 if len(listA) == 0 or len(listB) == 0:
 return []
 headA, tailA = listA[0], listA[1:]
 headB, tailB = listB[0], listB[1:]
 return [f(headA, headB)] + zipWith(f, tailA, tailB)

print zipWith(lambda x, y : x + y, [2,2,2,2], [3,3,3,3,3])
# [5,5,5,5]
# 结果列表长度由参数中两个列表更短的那个决定


JS 版：




const zipWith = f => xs => ys => {
 if (xs.length === 0 || ys.length === 0) return [];
 const [headX, ...tailX] = xs;
 const [headY, ...tailY] = ys;
 return [f(headX)(headY), ...zipWith(f)(tailX)(tailY)];
};


replicate


Python 版：




def replicate(n,x):
 if n <= 0:
 return []
 return [x] + replicate(n-1,x)

print replicate(4, 'hello')
# ['hello', 'hello', 'hello', 'hello']


JS 版：




const replicate = (n, x) => {
 if (n <= 0) return [];
 return [x, ...replicate(n - 1, x)];
};


reduce


Python 不鼓励用 reduce，我就不写了。


JS 版：




const reduce = (f, acc, arr) => {
 if (arr.length === 0) return acc;
 const [head, ...tail] = arr;
 return reduce(f, f(head, acc), tail);
};


quickSort


用递归来实现排序算法肯定不是最优的，但是如果处理数据量小的话，也不是不能用。


Python 版：




def quickSort(xs):
 if len(xs) <= 1:
  return xs
 pivot, rest = xs[0], xs[1:]
 smaller, bigger = [], []
 for x in rest:
 smaller.append(x) if x < pivot else bigger.append(x)
 return quickSort(smaller) + [pivot] + quickSort(bigger)

print quickSort([44,14,65,34])
# [14, 34, 44, 65]


JS 版：




const quickSort = list => {
 if (list.length === 0) return list;
 const [pivot, ...rest] = list;
 const smaller = [];
 const bigger = [];
 rest.forEach(x =>
 x < pivot "color: #ff0000">解决递归爆栈问题


由于我对 Python 还不是特别熟，这个问题只讲 JS 场景了，抱歉。


每次递归时，JS 引擎都会生成新的 frame 分配给当前执行函数，当递归层次太深时，可能会栈不够用，导致爆栈。ES6引入了尾部优化（TCO），即当递归处于尾部调用时，JS 引擎会把每次递归的函数放在同一个 frame 里面，不新增 frame，这样就解决了爆栈问题。


然而，V8 引擎在短暂支持 TCO 之后，放弃支持了。那为了避免爆栈，我们只能在程序层面解决问题了。 为了解决这个问题，大神们发明出了 trampoline 这个函数。来看代码：




const trampoline = fn => (...args) => {
 let result = fn(...args);
 while (typeof result === "function") {
 result = result();
 }
 return result;
};


给trampoline传个递归函数，它会把递归函数的每次递归计算结果保存下来，然后只要递归没结束，它就不停执行每次递归返回的函数。这样做相当于把多次的函数调用放到一次函数调用里了，不会新增 frame，当然也不会爆栈。


先别高兴太早。仔细看 trampoline 函数的话，你会发现它也要求传入的递归函数符合尾部调用的情况。那不符合尾部调用的递归函数怎么办呢？（ 比如我刚刚写的 JS 版 quickSort，最后 return 的结果里，把两个递归调用放在了一个结果里。这种情况叫 binary recursion，暂译二元递归，翻译错了勿怪 ）


这个问题我也纠结了很久了，然后直接去 Stack Overflow 问了，然后真有大神回答了。要解决把二元递归转换成尾部调用，需要用到一种叫 Continuous Passing Style (CPS) 的技巧。来看怎么把 quickSort 转成尾部调用:




const identity = x => x;

const quickSort = (list, cont = identity) => {
 if (list.length === 0) return cont(list);

 const [pivot, ...rest] = list;
 const smaller = [];
 const bigger = [];
 rest.forEach(x => (x < pivot "_blank" href="http://递归函数">这章内容。我不能保证比他讲的更清楚，就不讲了。


屠龙之技


虽然我将要讲的这个概念在 JS 中根本都用不到，但是我觉得很好玩，就加进来了。有些编程语言是不支持递归的（我本科不是学的计算机，不知道是哪些语言），那这时候如果我知道用递归可以解决某个问题，该怎么办？用 Y-combinator.


JS 实现：




function y(le) {
 return (function(f) {
 return f(f);
 })(function(f) {
 return le(function(x) {
 return f(f)(x);
 });
 });
}

const factorial = y(function(fac) {
 return function(n) {
 return n <= 2 "color: #ff0000">总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。

                                
                                

                                    递归算法,递归,递归函数 
                                
华山资源网 Design By www.eoogi.com