11.什么是递归在程序中，所谓递归就是函数直接或间接调用自己1.1直接调用自己functionf(){console.log(1);f();}1.2间接调用functionf1(){f2();}functionf2(){f1();}递归来讲，最重要的是跳出结构体，因为只有跳出结构体结构才能有结果。1.3所谓递归，就是递归思想的递归调用。写递归函数的时候，还是要转成自己的函数，再加一个函数f。如果是递归函数，也就是说函数体中的问题还是转换成f的形式。递归的思想是把一个问题转化为解决的问题来实现例子：1,2,3,4,...,100，累加结果先假设递归函数已经写好了，假设是foo，即foo(100)是求1到100的和，求递归关系，即n和n-1，或者n-2的关系：foo(n)==n+foo(n-1)varres=foo(100);varres=foo(99)+100；将递归结果转换为递归体函数foo(n){returnn+foo(n-1);}将100的计算转换为99将99的计算转换为98的计算...将2转换为1，并且1的结果为1，即：foo(1)is1递归体函数foo(n){return(n==1)return1;returnn+foo(n-1);}2。递归求值实例2.1算术数列1数列：求第n项的结果和前n项的和。序号从0开始先找第n项的值假设递归函数已经写好了，假设是fn。那么第n项就是fn(n)求递归关系：fn(n)==f(n-1)+2递归体函数fn(n){returnfn(n-1)+2;}求临界条件求n->n-1找n-1->n-2...找1->0找第0项，也就是1添加临界条件函数fn(n){if(n==0)return1;returnfn(n-1)+2;}假设前N项求和完成，sum(n)为前n项求和求递归关系：前n项求和等于对第n项+前n-1项求和得到递归体函数sum(n){returnfn(n)+sum(n-1);}求临界条件n==1结果为1和得到递归函数functionsum(n){if(n==0)return1;returnfn(n)+sum(n-1);}2.2算术数列2sequence:2,4,6,8,10第n项，第一项n项和第n项fu函数fn(n){if(n==0)return2;returnfn(n-1)+2;}前n项和函数sum(n){if(n==0)return2;returnsum(n-1)+fn(n);}2.3差分序列sequence:1,1,2,4,7,11,16,…求第n项，求前n项的和。求第n项，从0开始，假设已经得到结果fn，fn(10)为第10项求递推关系。第0项和第1项的差异为0=>fn(0)+0=fn(1)第1项和第2项的差异为1=>fn(1)+1=fn(2)第2项和第3项相差2=>fn(1)+2=fn(2)...n-1和第n项相差n-1=>fn(n-1)+n-1=fn(n)递归体很明显，临界条件是n==0=>1functionfn(n){if(n==0)return1;returnfn(n-1)+n-1;}如果从1开始，那么第n项就是假设已经得到结果fn，fn(10)是第10项，求第一项和第二项的递归关系，差为0=>fn(1)+0=fn(2)2nd第三项相差1=>fn(2)+1=fn(3)第三和第四项相差2=>fn(3)+2=fn(4)...第n-1项和n-th项相差n-1=>fn(n-1)+n-2=fn(n)临界条件n==1=>1前n个项目和函数sum(n){if(n==1)return1;returnsum(n-1)+fn(n);}2.4斐波那契数列这个是最常见的，问的最多的知道的之一ledgeininterviews，斐波那契数列为：1,1,2,3,5,8,13,21,34,55,89,...求递归关系fn(n)==fn(n-1)+fn(n-2),所以递归函数为functionfib(n){if(n==0||n==1)return1;returnfib(n-1)+fib(n-2);}3.高级递归3.1阶乘计算阶乘是递归编程的一个经典例子。阶乘是一种操作。计算某个数的阶乘就是用该数乘以所有较小的数，包括1.数。例如，factorial(5)相当于5*4*3*2*1，factorial(3)相当于3*2*1。5！是1*2*3*4*5。0的阶乘为1，阶乘从1开始。求n的阶乘functionfoo(n){if(n==1)return1;returnfoo(n-1)*n;}console.log(foo(5));//120与前1到的和100递归函数很相似，不过是变种3.2求幂就是求某个数2*22的2次方的平方，求n的2次方的m次方，最后求得到一个函数power(n,m)n的m次方是n的m乘法，即n乘以n的(m-1)乘法functionpower(n,m){if(m==1)returnn;returnpower(n,m-1)*n;}console.log(power(2,3));//84.递归深拷贝如果要实现深拷贝，那么就需要考虑复制对象的属性，属性的属性...4.1简单实现如果要实现：假设clone(o1,o2)有已经实现，将对象o2的一个成员复制到o1简单算法，将o2的属性复制到o1functionclone(o1,o2){for(varkino2){o1[k]=o2[k];}}求递归关系，或将其简化为已解决的问题。假设方法已经实现了，问一下，如果o2[k]是对象，继续使用这个方法，所以需要考虑o2[k]是什么，如果是引用类型，就用clone()函数再次如果o2[k]不是引用类型，则直接赋值functionclone(o1,o2){for(varkino2){if(typeofo2[k]=='object'){o1[k]={};clone(o1[k],o2[k]);}else{o1[k]=o2[k];}}}varperson1={name:'张三',children:[{name:'张一'},{name:'张二'},{name:'王三'}]};varperson2={};clone(person2,person1);4.2复杂实现clone(o)->newObjfunctionclone(o){vartemp={};for(varkino){if(typeofo[k]=='object'){temp[k]=clone(o[k]);}else{temp[k]=o[k];}}returntemp;}varperson1={name:'张三',children:[{name:'张一'},{name:'张二'},{name:'王三'}]};varperson2=clone(person1);//修改一个看另一个是否也修改了person2.name='李四';person2.children[0].name='王小虎';人2。children[1].name='张大虎';person2.children[2].name='李长虎';4.3getElementsByClassName方法的递归实现有如下DIV结构：
