递归
什么是递归
在程序中，所谓的递归，就是函数自己直接或间接的调用自己。调用自己分两种：
直接调用自己
间接调用自己
就递归而言最重要的就是跳出结构，因为跳出了才可以有结果.
化归思想
化归思想：将一个问题由难化易，由繁化简，由复杂化简单的过程称为化归，它是转化和归结的简称。
递归思想就是将一个问题转换为一个已解决的问题来实现
假如有一个函数f, 如果它是递归函数的话, 那么也就是说函数体内的问题还是转换为 f的形式.
function f() {
... f( ... ) ...
}
例子:
1, 2, 3, 4, 5, ..., 100 求和
首先假定递归函数已经写好, 假设是
foo. 即foo(100)就是求1到100的和寻找递推关系. 就是
n与n-1, 或n-2之间的关系:foo( n ) == n + foo( n - 1 )
var res = foo(100);
var res = foo(99) + 100;
将递推结构转换为递归体
function foo(n){
return n + foo( n - 1 );
}
上面就是利用了化归思想：
将 求 100 转换为 求 99
将 求 99 转换为 求 98
...
将求 2 转换为 求 1
求 1 结果就是 1
即: foo( 1 ) 是 1
将临界条件加到递归体中(求1的结果为1)
function foo( n ) {
if ( n == 1 ) return 1;
return n + foo( n - 1 );
}
练习:
求 1, 3, 5, 7, 9, ... 第
n项的结果与前n项和. 序号从0开始
先看求第n项
首先假定递归函数已经写好, 假设是
fn. 那么第n项就是fn(n)找递推关系:
fn(n) == f(n-1) + 2递归体
function fn(n) {
return fn(n-1) + 2;
}
找临界条件
求 n -> n-1
求 n-1 -> n-2
...
求 1 -> 0
求 第 0 项, 就是 1
加入临界条件
function fn( n ) {
if ( n == 0 ) return 1;
return fn( n-1 ) + 2;
}
再看求前n项和
假设已完成, sum( n ) 就是前 n 项和
找递推关系: 前 n 项和 等于 第 n 项 + 前 n-1 项的和
递归体
function sum( n ) {
return fn( n ) + sum( n - 1 );
}
找临界条件
n == 1结果为 1
加入临界条件
function sum( n ) {
if (n == 0) return 1;
return fn(n) + sum(n - 1);
}
练习
2, 4, 6, 8, 10 第 n 项与 前 n 项和
解题方法和上一题一样。
练习
现有数列: 1, 1, 2, 4, 7, 11, 16, … 求 第 n 项, 求前 n 项和.
求第n项
假设已经得到结果 fn, fn( 10 ) 就是第 10 项
找递推关系
0, 1 => fn( 0 ) + 0 = fn( 1 )
1, 2 => fn( 1 ) + 1 = fn( 2 )
2, 3 => fn( 2 ) + 2 = fn( 3 )
...
n-1, n => fn( n-1 ) + n - 1 = fn( n )
递归体也就清楚了
临界条件是 n == 0 => 1
function fn( n ) {
if ( n == 0 ) return 1;
return fn( n-1 ) + n - 1;
}
前n项和
function sum( n ) {
if ( n == 0 ) return 1;
return sum( n - 1 ) + fn( n );
}
练习
Fibonacci 数列: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 求其第 n 项.
递推关系:fn(n) == fn(n-1) + fn(n - 2)
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开始。
求n的阶乘
function foo ( n ) {
if ( n == 1 ) return 1;
return foo( n - 1 ) * n;
}
练习
求幂
求幂就是求 某一个数 几次方
2*2 2 的 平方, 2 的 2 次方
求 n 的 m 次方
最终要得到一个函数 power( n, m )
n 的 m 次方就是 m 个 n 相乘 即 n 乘以 (m-1) 个 n 相乘
function power ( n, m ) {
if ( m == 1 ) return n;
return power( n, m - 1 ) * n;
}