最大值的递归算法
对于一个数组 有A[ 1...n ]
算法调用的时候调用max(n)
max（i） if i = 1 return A[i] else if A[i]>max(i-1) return A[i] else return max(i-1) end if end if
平均值的递归算法
对于数组 a[ 1...n ]
sum 初值为 0
index 初值则为1
调用该算法使用 Ave（a,sum,index）
Ave(int a[],int sum,int index) if(index > n)
return sum/(index-1) else return Ave(a,sum+=a[index],index+1)
汉诺塔的 递归算法
void move(int n,char left,char middle,char right) { if(n==1)//移动1号盘 cout<<n<<"号盘"<<"："<<left<<"→"<<right<<endl; else{ move(n-1,left,right,middle); cout<<n<<"号盘"<<"："<<left<<"→"<<right<<endl;//移动n号盘 move(n-1,middle,left,right); } }
动态规划问题
Lcs 最长子序列 递归式
ai = bi L[i,j] = L[i-1,j-1] + 1; ai!= bi L[i,j] = max{L[i-1,j],L[i,j-1]}
Floyd 最短路径 递归式
0- 1 背包的 递归式
si > j V[i,j] = V[i-1,j] //当前背包大小小于物品的体积 si =< j V[i,j] = max{V[i-1,j],V[i-1,j-si]+vi}//当前的背包大小大于等于物品的体积
当 0 - 1 背包 变成 完全背包的 时候
可以修改以上的递归式 修改为 一下 格式k = si/j
si > j V[i,j] = V[i-1,j] //当前背包大小小于物品的体积 si =< j V[i,j] = max{V[i-1,j],V[i-1,j-k*si]+k*vi}//当前的背包大小大于等于物品的体积
3着色问题 的 递归算法
输入：无向图G＝(V,E) 输出：图的结点3着色向量c[1..n]，1≤c[k]≤3（1≤k≤n）。 1. GraphColorRec(1) 过程 GraphColorRec(k) 1. for color←1 to 3 2. c[k]←color 3. if c[1..k]为合法着色 then //部分解或解 4. if k＝n then //解 5. output c[1..n] and exit 6. else //部分解 7. GraphColorRec(k+1) //进入下一个结点 8. end if 9. end if 10. end for
4皇后问题 递归算法
输入：空 输出：对应于4皇后问题的向量c[1..4]（全局量） 1. advanced(1) 过程 advanced(k) 1. for col←1 to 4 //最多只有4列 2. c[k]←col 3. if c[1..k]是解 then //部分解或解 4. if k=4 then //完全解 5. output c[1..4] and exit 6. else //部分解 7. advanced(k+1) //移至下一行 8. end if 9. end if 10. end for
