js中的递归算法

浅浅的花香味﹌ 2022-12-08 12:52 134阅读 0赞

#### js递归定义： ####

*  递归函数就是在函数体内调用本函数
 *  递归函数的使用要注意函数终止条件，避免进入死循环

#### 简单的递归实例 ####

**1.求1,2,3,…n的和**

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

**2.求1,3,5,7,…第n项和前n项的和**

先求出第n项的值

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

接着求前n项的和

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);
    }

**3.求2,4,6,8,…第n项和前n项的和**

这个跟上面的奇数实例差不多，只是临界条件不一样。  
偶数项的临界条件为

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);
    }

#### Fibonacci数列(斐波那契数列) ####

1,1,2,3,5,8,13,21,34,55,89…求第 n 项  
后一项为前两项的和

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

#### 稍微高级那么一丢丢的递归 ####

**1.求1,2,3,…到n的阶乘**

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

**2.求 n 的 m 幂次方**

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

#### 使用递归实现深拷贝 ####

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

要实现深拷贝那么就需要考虑将对象的属性, 与属性的属性,都拷贝过来