JS中的递归递归基础

递归的概念

在程序中函数直接或间接调用自己
1. 直接调用自己
2. 间接调用自己
跳出结构,有了跳出才有结果

递归的思想

递归的调用,最终还是要转换为自己这个函数
1. 如果有个函数foo,如果他是递归函数,到最后问题还是转换为函数foo的形式
2. 递归的思想就是将一个未知问题转换为一个已解决的问题来实现

function foo(){
    ...foo(...)...
}

递归的步骤(技巧)

假设递归函数已经写好
寻找递推关系
将递推关系的结构转换为递归体
将临界条件加入到递归体中

简单递归练习

求1-100的和

分析:

假设递归函数已经写好为sum,既sum(100),就是求1-100的和
寻找递推关系: 就是 n 与 n-1 ,或 n-2 之间的关系
sum(n) == sum(n-1) + n
```
var res = sum(100);
var res = sum(99) + 100;
```

将递归结构转换成递归体

function sum(n){
    return sum(n-1) + n;
}

将临界条件加入到递归中

求100 转换为 求99
求99 转换为 求98
求98 转换为 求97
...
求2 转换为 求1
求1 转换为 求1
即 sum(1) = 1

递归函数

function sum(n){
    if(n==1) return 1;
    return sum(n-1) + n;
}

求 1,3,5,7,9,...第n项的结果和前n项和,序号从0开始

分析

假设递归函数已经完成foo(n),得到奇数
递归关系:

foo(n) = foo(n-1)+2

递归体

function foo(n){
    return foo(n) = sum(n-1)+2;
}

跳出条件

 foo(n) = foo(n-1) + 2
 foo(1) = foo(0) + 2
 foo(0) = 1

递归函数

function foo(n){
    if(n == 0) return 1;
    return foo(n-1) + 2;
}

前 n 项的和

分析

假设完成,sum(n)就是前n项的和
递推关系foo(n) = sum(n) + 第n-1项之前的和
递归体


    function sum(n){
        return foo(n) + sum(n-1);
    }

临界条件n == 1 ,结果为1
递归函数

	function foo(n){
          if(n == 0) return 1;
          return foo(n-1) + 2;

      }

   function sum(n){
          if(n == 0) return 1;
          return foo(n) + sum(n-1);
   }

求 2,4,6,8,10... 第n项与前n项之和

分析

假设已知函数 fn(n)为第n项,sum(n)为前n项之和
递归关系

  fn(n) = fn(n-1) + 2
  sum(n) = fn(n) + sum(n-1)

递归体

  function fn(n){
      return fn(n) = (n-1) + 2
  }
  function sum(n){
      return sum(n) = fn(n) + sum(n-1);
  }

临界条件

    fn(0) = 2
    sum(0) = 2

递归函数

    function fn(n){
        if(n == 0) return 2;
        return fn(n-1) + 2;
    }
    function sum(n){
        if(n==0) return 2;
        return fn(n) + sum(n-1);
    }

数列 1,1,2,4,7,11,16...求第 n 项,求前n项和

分析

假设已知函数 foo(n) 为第n项
递归关系
从第 0 项开始计算
第 0 项, 1 => foo(0) + 0 = foo(1)
第 1 项, 2 => foo(1) + 1 = foo(2)
第 2 项, 3 => foo(2) + 2 = foo(3)
...
第 n-1 项, n => foo(n-1) + n-1 = foo(n)
foo(n) = foo(n-1) + n-1

从第 1 项开始计算
第 1 项, 2 => fn( 1 ) + 0 = fn( 2 )
第 2 项, 3 => fn( 2 ) + 1 = fn( 3 )
第 3 项, 4 => fn( 3 ) + 2 = fn( 4 )
...
foo(n) = fn(n-1) + n - 2
如果从 0 开始

    0  1  2  3  4  5   6
    1, 1, 2, 4, 7, 11, 16,

如果从 1 开始

    1  2  3  4  5  6   7
    1, 1, 2, 4, 7, 11, 16

递归体

    function foo(n){
        return foo(n-1)+n-1;
    }

临界条件

    foo(0) == 1
    foo(1) == 1

递归函数

    function foo(n){
        if(n == 0) return 1;
        return foo(n-1) + n -1;
    }

分析

假设已知函数 sum(n)为前n项和
递归关系sum(n) = foo(n) + sum(n-1)
递归体

    function sum(n){
        return foo(n) + sum(n-1);
    }

临界条件

sum(0) = 1
5. 递归函数

    function sum(n){
        if(n == 0) return 1;
        return foo(n) + sum(n-1);
    }

Fibonacci数列(斐波那契数列)

1,1,2,3,5,8,13,21,34,55,89...求第 n 项

分析

假设已知 fib(n) 为第 n 项
递归关系
fib(n) = fib(n-1) + fib(n-2)
递归体

    function fib(n){
        return fib(n-1)+fib(n-2);
    }

临界条件

   fib(0) == 1
   fib(1) == 1

递归函数

    function fib(n){
        if(n == 0 || n ==1) return 1;
        return fib(n-1) + fib(n-2);
    }

高级递归练习

阶乘

概念:

阶乘是一个运算, 一个数字的阶乘表示的是从 1 开始累乘到这个数字.
例如 3! 表示 1 * 2 * 3. 5! 就是 1 * 2 * 3 * 4 * 5. 规定 0 没有阶乘,
阶乘从 1 开始.
分析:
1. 假设已知 foo(n) 为 1-n 的积
2. 递归关系
  foo(n) = foo(n-1) * n
3. 递归体
```
    function foo(n){
        return foo(n-1) * n
    }
```
临界条件foo(1) == 1
递归函数

    function foo(n){
        if( n == 1) return 1;
        return foo(n - 1) * n;
    }

求幂

概念:
1. 求幂就是求某一个数几次方
2. 2*2 2 的平方, 2 的 2 次方
3. 求 n 的 m 次方
4. 最终要得到一个函数 power( n, m )
5. n 的 m 次方就是 m 个 n 相乘即 n 乘以 (m-1) 个 n 相乘

分析

假设已知函数 power(n,m) 为 n 的 m 次幂
递归关系
power(n,m-1) * n
递归体

    function power(n,m){
        return power(n,m-1) * n;
    }

临界条件

    m == 1 ,return n
    m == 0 ,reutnr 1

递归函数

    function power(n,m){
        if(m == 1) return n;
        return power(n,m-1) * n;
    }

深拷贝,使用递归方式

概念:

如果拷贝的时候, 将数据的所有引用结构都拷贝一份, 那么数据在内存中独立就是深拷贝(内存隔离,完全独立)
如果拷贝的时候, 只针对当前对象的属性进行拷贝, 而属性是引用类型这个不考虑, 那么就是浅拷贝
拷贝: 复制一份. 指将对象数据复制.
在讨论深拷与浅拷的时候一定要保证对象的属性也是引用类型.

实现方法:

如果要实现深拷贝那么就需要考虑将对象的属性, 与属性的属性,都拷贝过来
分析(2个参数,简单实现)
1. 假设已经实现 clone ( o1, o2),将对象 o2 的成员拷贝一份交给 o1
2. 递推关系:
  1. 混合方法,将 o2 的成员拷贝到 o1 中
  2. 假设方法已经实现,如果 o2[key] 是对象
  3. 继续使用这个方法
  4. 需要考虑 o2[key] 是引用类型,再一次使用clone函数
  5. 如果 o2[key] 不是引用类型,那么直接赋值
```
    function clone( o1, o2){
        for(var key in o2){
            o1[key] = o2[key];
        }
    }
```
  1. 临界条件, 因为是 for in 循环,没有成员遍历时,自动结束
  2. 递归函数
```
    function clone(o1,o2){
        for(var key in o2){
            if(typeof o2[key] == 'object'){
                o1[key] = {};
                clone(o1[key],o2[key])
            }else{
                o1[key] = o2[key];
            }
        }
    }
```

复杂实现(一个参数)
原理: clone(o) = new Object; 返回一个对象
递归函数

    function clone(o){
        var temp = {};
        for(var key in o){
            if(typeof o[key] == 'object'){
                temp[key] = clone(o[key]);
            }else{
                temp[key] = o[key];
            }
        }
        return temp;
    }

使用递归实现 getElementsByClassName

html结构:

    <div>
    	<div>1
    		<div class="c">2</div>
    		<div>3</div>
    	</div>
    	<div class="c">4</div>
    	<div>5
    		<div>6</div>
    		<div class="c">7</div>
    	</div>
    	<div>8</div>
    </div>

分析
1. 实现一个方法byClass()需要的参数是:
- node: 在某个节点上寻找元素
- className: 需要寻找的className
- arr: 找到的元素存储到这个数组中
1. 遍历 node 的子节点,
2. 查看这个子节点是否还有子节点,如果没有直接存储到数组中,如果有就继续递归

    var arr = [];
    function byClass(node, className, arr){
        //得到传入节点的所有子节点
        var lists = node.childNodes;
        for(var i = 0;i< lists.length;i++){
            //判断是否有相同className元素
            if(arr[i],className == className){
                arr.push(arr[i]);
            }
            //判断子节点是否还有子节点
            if(arr[i].childNodes.length > 0){
                byClass(arr[i],className,arr);
            }
        }
    }

使用递归查找树结构父级

handleSelectedNodes(tree) {
      const path = []
      function treeFindPath(tree, func, path = []) {
        if (!tree) {
          return []
        }
        for (const data of tree) {
          path.push(data)
          if (func(data)) {
            return path
          }
          if (data.children) {
            const findChildren = treeFindPath(data.children, func, path)

            if (findChildren.length) {
              return findChildren
            }
          }
          path.pop()
        }
        return []
      }
      treeFindPath(tree, (data) => data.name === this.selectCategory, path)
      return path
    }

JS中的递归 递归基础