我对递归的初步了解
论道无法目前无法用markdown语法
http://note.youdao.com/noteshare?id=7a2cfa7d7397bbd77cb6a511dcb61ce6
可以直接访问链接
# 递归
## 简单递归
```
function factorial(n){
if(n == 1 ){return 1}
return n*factorial(n-1)
}
function fib(n){
if( n == 0 ){return 0}
if( n == 1 || n ==2){return 1}
return fib(n-1) + fib(n-2)
}
```
以上是简单的一看大概就数学类递归,
递归有很明显的两个组成部分
先看出来的结果,结果必然是同名函数或方程(没有最终输出之前),
然后必须要有输出的结果(一定要有递归结束条件)
## 递归应用
假定有1美分,5美分,10美分,25美分,50美分的零钱无限多，试把任意钱换成零钱，写一个函数计算有多少种换法。
请将代码写在count_change函数里，返回有多少种换算方法。该函数有一个参数，传入的是一个数字，单位是美分，比如，1美元，传入的是100美分。
```
function count_change(amount, valueIndex=5){
//首先程序不是人,要一步一步进行运算
if(amount < 0 || valueIndex <= 0 ){return 0}
//结束条件一,钱数到负数,或者已经没有下一个值给我用了,说明此路不通
if(amount === 0){return 1}
//结束条件而,钱刚刚好数完,说明这是一种方法 输出1
//如果上面两种条件没有达到,说明程序要进行下一步,
//分解成两个结果的组合
//一个是减去最大的数值后,还剩下几种
//一个是下一个币值有几种
return count_change_rest_value(amount,valueIndex) + count_change_next_value(amount,valueIndex)
}
function count_change_rest_value(amount,valueIndex){
var val = valueSpace[valueIndex]
var rest = amount - val
//上面求得了剩下的数值,然后重新放到能实现结果的方程
return count_change(rest , valueIndex)
}
function count_change_next_value(amount,valueIndex){
//直接进入到下一个币值的计算
return count_change(amount,valueIndex-1)
}
//用对象实现逻辑的对应
var valueSpace = {
5:50,
4:25,
3:10,
2:5,
1:1,
}
```
### 思考题
写一个f函数,满足下面的需求:
如果 n < 3，那么f(n) = n
如果 n >= 3, 那么 f(n) = f(n-1)+2f(n-2)+3f(n-3)
伪代码
f(n){
如果小于n 输出 n
如果大于n 输出 怎么样输出同名函数
}
## 难度加大的递归
实现pascal_triangle函数，以打印帕斯卡三角(即杨辉三角)
> 1
> 1 1
> 1 2 1
> 1 3 3 1
> 1 4 6 4 1
这个问题,如果用迭代写非常简单,无非是根据上一个数组生成当前数组,但是如果是用递归,最难的地方是如何复用当前的函数/方程
我之前用了狗屁膏药的方式实现过一个,但是为了颜面,在这里用点脑子,就是把三角补充成矩阵
```
function pascal_triangle(n, prvRect=[1]){
//如果一开始的话 是没有输入数组,所以用了默认值
if(prvRect.length == n){return prvRect}
//结果仅仅当发现矩阵 大小是目标长度才输出
nextRect = getPrvRectFillZero(prvRect)
//递归过程中 给出了上一个矩阵,补充零
nextRect.push(getNextArr(prvRect))
//上一个矩阵,再加上新的数组就是我想要的杨辉三角
return pascal_triangle(n,nextRect)
}
function getPrvRectFillZero(prvRect){
if(prvRect.length == 1){ return [[1,0]] }
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
for(var i = 0; i < prvRect.length-1; i++) {
prvRect.push(0)
}
return prvRect
}
function getNextArr(prvRect){
if(prvRect.length == 1){ return[1,1]}
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
var nextArr =
var prvArr = prvRect[prvRect.length-1]
prvArr.push(0)
for(var i = 0; i < prvArr.length; i++) {
var num = getTwo(i,prvArr)
//这里的数值是根据一个数组生成,就这样放着,等会实现
nextArr.push(num)
}
return nextArr
}
function getTwo(i,arr){
if(arr.length == 1 || i==0 ){return 1}
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
return arr[i-1] + arr
[i] //如果把需求脱离出来,就发现每一步都很简单
}
```
### 思考题
实现gcd函数，用欧几里得法求两个参数的最大公约数 这一算法基于下面的观察，如果r是a和b的余数，那么a和b的公约数正好也是b和r的公约数，因此我们可以借助等式
gcd(a,b) = gcd(b,r)
伪代码
gcd(a,b){
当 b 等于零 输出
求出a b的余数 a%b
输出 怎么样的gcd 接受什么样的参数
}[/i]
http://note.youdao.com/noteshare?id=7a2cfa7d7397bbd77cb6a511dcb61ce6
可以直接访问链接
# 递归
## 简单递归
```
function factorial(n){
if(n == 1 ){return 1}
return n*factorial(n-1)
}
function fib(n){
if( n == 0 ){return 0}
if( n == 1 || n ==2){return 1}
return fib(n-1) + fib(n-2)
}
```
以上是简单的一看大概就数学类递归,
递归有很明显的两个组成部分
先看出来的结果,结果必然是同名函数或方程(没有最终输出之前),
然后必须要有输出的结果(一定要有递归结束条件)
## 递归应用
假定有1美分,5美分,10美分,25美分,50美分的零钱无限多，试把任意钱换成零钱，写一个函数计算有多少种换法。
请将代码写在count_change函数里，返回有多少种换算方法。该函数有一个参数，传入的是一个数字，单位是美分，比如，1美元，传入的是100美分。
```
function count_change(amount, valueIndex=5){
//首先程序不是人,要一步一步进行运算
if(amount < 0 || valueIndex <= 0 ){return 0}
//结束条件一,钱数到负数,或者已经没有下一个值给我用了,说明此路不通
if(amount === 0){return 1}
//结束条件而,钱刚刚好数完,说明这是一种方法 输出1
//如果上面两种条件没有达到,说明程序要进行下一步,
//分解成两个结果的组合
//一个是减去最大的数值后,还剩下几种
//一个是下一个币值有几种
return count_change_rest_value(amount,valueIndex) + count_change_next_value(amount,valueIndex)
}
function count_change_rest_value(amount,valueIndex){
var val = valueSpace[valueIndex]
var rest = amount - val
//上面求得了剩下的数值,然后重新放到能实现结果的方程
return count_change(rest , valueIndex)
}
function count_change_next_value(amount,valueIndex){
//直接进入到下一个币值的计算
return count_change(amount,valueIndex-1)
}
//用对象实现逻辑的对应
var valueSpace = {
5:50,
4:25,
3:10,
2:5,
1:1,
}
```
### 思考题
写一个f函数,满足下面的需求:
如果 n < 3，那么f(n) = n
如果 n >= 3, 那么 f(n) = f(n-1)+2f(n-2)+3f(n-3)
伪代码
f(n){
如果小于n 输出 n
如果大于n 输出 怎么样输出同名函数
}
## 难度加大的递归
实现pascal_triangle函数，以打印帕斯卡三角(即杨辉三角)
> 1
> 1 1
> 1 2 1
> 1 3 3 1
> 1 4 6 4 1
这个问题,如果用迭代写非常简单,无非是根据上一个数组生成当前数组,但是如果是用递归,最难的地方是如何复用当前的函数/方程
我之前用了狗屁膏药的方式实现过一个,但是为了颜面,在这里用点脑子,就是把三角补充成矩阵
```
function pascal_triangle(n, prvRect=[1]){
//如果一开始的话 是没有输入数组,所以用了默认值
if(prvRect.length == n){return prvRect}
//结果仅仅当发现矩阵 大小是目标长度才输出
nextRect = getPrvRectFillZero(prvRect)
//递归过程中 给出了上一个矩阵,补充零
nextRect.push(getNextArr(prvRect))
//上一个矩阵,再加上新的数组就是我想要的杨辉三角
return pascal_triangle(n,nextRect)
}
function getPrvRectFillZero(prvRect){
if(prvRect.length == 1){ return [[1,0]] }
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
for(var i = 0; i < prvRect.length-1; i++) {
prvRect.push(0)
}
return prvRect
}
function getNextArr(prvRect){
if(prvRect.length == 1){ return[1,1]}
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
var nextArr =
var prvArr = prvRect[prvRect.length-1]
prvArr.push(0)
for(var i = 0; i < prvArr.length; i++) {
var num = getTwo(i,prvArr)
//这里的数值是根据一个数组生成,就这样放着,等会实现
nextArr.push(num)
}
return nextArr
}
function getTwo(i,arr){
if(arr.length == 1 || i==0 ){return 1}
//由于下面用到循环,所以如果prvRect的长度不大于1就出bug,特殊值用子程序剔除
return arr[i-1] + arr
[i] //如果把需求脱离出来,就发现每一步都很简单
}
```
### 思考题
实现gcd函数，用欧几里得法求两个参数的最大公约数 这一算法基于下面的观察，如果r是a和b的余数，那么a和b的公约数正好也是b和r的公约数，因此我们可以借助等式
gcd(a,b) = gcd(b,r)
伪代码
gcd(a,b){
当 b 等于零 输出
求出a b的余数 a%b
输出 怎么样的gcd 接受什么样的参数
}[/i]
