递归函数

递归函数就是对自身函数调用的过程。

递归必须有2部分组成

  1. 执行递归调用自身
  2. 递归调用的终止条件

两个条件缺一不可，如果没有终止条件，会陷入无限递归。

求解递归问题

使用递归运算阶乘

  1. const fib = (n)=>{
  2.     if(n < 2) return 1;
  3.   else n * fib(n - 1)
  4. }
  5. console.log(fib(5))

递归解析树型数据结构

比如解析DOM结构树

  1. function find (n) {  //统计指定节点及其所有子节点的元素个数
  2.     var l = 0;  //初始化计数变量
  3.     if (n.nodeType == 1) l ++;  //如果是元素节点，则计数
  4.     var child = n.childNodes;  //获取子节点集合
  5.     for (var i = 0; i < child.length; i ++) {  //遍历所有子节点
  6.         l += find (child[i]);  //递归运算，统计当前节点下所有子节点数
  7.     }
  8.     return l;  //返回节点数
  9. }
  10. window.onload = function () {
  11.     console.log(find(document.body));  //返回2，即body和script两个节点
  12. }

递归求解复杂的嵌套问题

比如汉诺塔,参数说明：n 表示金片数；a、b、c 表示柱子，注意排列顺序。

  1. function hanoi (n,a,b,c) {
  2.     if (n == 1) {  //当为一片时，直接移动
  3.         console.log("移动 【盘子" + n + "】从【" + a + "柱】到【" + c + "柱】<br>");
  4.     } else {
  5.         hanoi(n - 1, a, c, b);  //调整参数顺序。让参数a移给b
  6.         console.log("移动 【盘子" + n + "】从【" + a + "柱】到【" + c + "柱】<br>");
  7.         hanoi(n - 1, b, a, c);  //调整顺序，让参数b移给c
  8.     }
  9. }
  10. hanoi(3, "A", "B", "C");  //调用汉诺塔函数

尾递归优化

尾递归是递归调用的优化算法。
一般递归调用过程会形成一个调用函数链条，父层函数执行会依赖子函数结果，当子级函数调用执行完成，父层函数才会执行完成然后销毁，这样会形成一个调用栈，当调用层级过深，会造成内存溢出，程序崩溃。
尾递归的每层函数不再需要下层函数执行完成的结果就会销毁调用栈记录。每层函数执行都会返回执行结果

  1. // 普通的线性递归
  2. function f (n) {
  3.     return (n == 1) ? 1 : n * f (n - 1);
  4. }
  5. console.log(f(5));  //120
  7. // 当 n=5 时，线性递归的递归过程如下。
  8. f (5) = {5 * f(4)}
  9.       = {5 * {4 * f(3) }}
  10.       = {5 * {4 * {3 * f(2)}}}
  11.       = {5 * {4 * {3 * {2 * f(1)}}}}
  12.       = {5 * {4 * {3 * {2 *1}}}}
  13.       = {5 * {4 * {3 *2}}}
  14.       = {5 * {4 * 6}
  15.       = {5 * 24}
  16.       = 120
  1. //使用尾递归优化
  2. function f (n, a) {
  3.     return (n == 1) ? a : f (n - 1, a * n);
  4. }
  5. console.log(f(5, 1));  //120
  7. // 尾递归的递归过程
  8. f (5) = f (5, 1)
  9.       = f (4, 5)
  10.       = f (3, 20)
  11.       = f (2, 60)
  12.       = f (1, 120)
  13.       = 120

尾递归是递归的一种类型，不过其具有迭代算法的特性，可以将尾递归改为迭代执行。

  1. var n = 5;
  2. var w = 1;
  3. for (var i = 1; i <= 5; i ++) {
  4.     w = w * i;
  5. }
  6. console.log(w);

尾递归由于直接返回值，不需要保存临时变量，所以性能不会产生线性增加，同时 JavaScript 引擎会将尾递归形式优化成非递归形式。

递归与迭代的区别

递归和迭代都是循环的一种算法，让程序可以多次执行。有以下不同点

  • 递归是重复调用函数自身实现循环，迭代是通过循环结构实现。
  • 在结束方式上，递归是满足终止条件时逐层返回再结束。迭代是使用计数器进行结束循环。
  • 执行效率上，迭代的性能高于递归。递归使用了大量的系统资源，层级过深会系统崩溃。
  • 在实现上，递归会更容易理解，更容易把函数转化程序。迭代执行效率高，但是不易理解和编程。

实际开发应用，尽量少使用递归，递归都可以用迭代替换

斐波那契数列

递归函数

  1. // 正常的递归，非优化的，调用2次函数，需要两个变量
  2. function Fibonacci(n) {
  3.     if (n < 2) {
  4.         return n;
  5.     }
  6.     return Fibonacci(n - 1) + Fibonacci(n - 2);
  7. }
  8. console.log(Fibonacci(43));
  10. // 耗时4.548s
  11. let fibx = (n)=>{
  12.     return n < 2 ? n : fib(n - 1) + fib(n - 2);
  13. };
  14. console.log(fibx(43));
  16. // 优化后的递归，ok尾递归调用。耗时0.048s
  17. let fib = (n, s1, s2)=>{
  18.     return n <= 2  ? s2 : fib(n - 1, s2, s1 + s2);
  19. };
  20. console.log(fib(43, 1, 1));

如果返回的是包含2个执行函数 fib(n - 1) + fib(n - 2)，则尾递归需要定义2个变量。

使用迭代改写斐波那契数列递归

  1. var fibonacci = function (n) {
  2.     var a = [0, 1];  //记录数列的数组，第1、2个元素值确定
  3.     for (var i = 2; i <= n; i ++) {  //从第 3 个数字开始循环
  4.         a.push(a[i - 2] + a[i - 1]);  //计算新数字，并推入数组
  5.     }
  6.     return a[n];  //返回指定位数的数列结果
  7. };
  8. console.log(fibonacci(19));  //4181