## 什么是递归
在程序中, 所谓的递归, 就是函数自己直接或间接的调用自己.
1. 直接调用自己2. 间接调用自己
就递归而言最重要的就是跳出结构. 因为跳出了才可以有结果.
## 所谓的递归就是化归思想
递归的调用, 写递归函数, 最终还是要转换为自己这个函数.
假如有一个函数 f, 如果它是递归函数的话, 那么也就是说 函数体内的问题还是转换为 f 的形式.
递归思想就是将一个问题转换为一个已解决的问题来实现
1. 首先假定递归函数已经写好, 假设是 foo. 即 foo( 100 ) 就是求 1 到 100 的和2. 寻找递推关系. 就是 n 与 n-1, 或 n-2 之间的关系: foo( n ) == n + foo( n - 1 ) ``` var res = foo( 100 ); var res = foo( 99 ) + 100;```3. 将递推结构转换为 递归体``` function foo( n ) { return n + foo( n - 1 ); }``` * 将 求 100 转换为 求 99 * 将 求 99 转换为 求 98 * ... * 将求 2 转换为 求 1 * 求 1 结果就是 1 * 即: foo( 1 ) 是 14. 将临界条件加到递归体中``` function foo( n ) { if ( n == 1 ) return 1; return n + foo( n - 1 ); }```
练习: 求 1, 3, 5, 7, 9, ... 第 n 项的结果与前 n 项和. 序号从 0 开始
**求第 n 项的**1. 首先假定递归函数已经写好, 假设是 fn. 那么 第 n 项就是 fn( n )2. 找递推关系: fn( n ) == f( n - 1 ) + 23. 递归体``` function fn( n ) { return fn( n-1 ) + 2; }```4. 找临界条件 * 求 n -> n-1 * 求 n-1 -> n-2 * ... * 求 1 -> 0 * 求 第 0 项, 就是 15. 加入临界条件``` function fn( n ) { if ( n == 0 ) return 1; return fn( n-1 ) + 2; }```
**前n项和**1. 假设已完成, sum( n ) 就是前 n 项和2. 找递推关系: 前 n 项和 等于 第 n 项 + 前 n-1 项的和3. 得到递归体``` function sum( n ) { return fn( n ) + sum( n - 1 ); } ```4. 找临界条件 * n == 1 结果为 15. 得到递归函数``` function sum( n ) { if ( n == 0 ) return 1; return fn( n ) + sum( n - 1 ); } ```
转载于:https://www.cnblogs.com/yanghaot/p/5745110.html
相关资源：各显卡算力对照表！