递归

2024-04-12 14:08:32

PART 1-要点

1.1递归式

将原问题划分成子问题

1.2 递归出口

终止的条件

1.3 界函数

问题规模变化的函数

！注意：由于函数的局部变量是存在栈上的，如果有体积大的局部变量比如数组而递归如果有体积大的局部变量，比如数组，而递归层次又可能很深的情况下，也许会导致栈溢出，因此可以考虑使用全局数组或动态分配数组

PART 2-例题

2.1 汉诺塔

2.2 放苹果（POJ 1664）

问题：m个苹果，n个盘子，有多少种不同的放法？（盘子和苹果没有编号，即123和321是一种方法）

算法：设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
①当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响，即 f(m,n) = f(m,m)
②当n<=m：不同的放法可以分成两类：
1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即 f(m,n) = f(m-n,n). 而总的放苹果的放法数目等于两者的和，即 f(m,n)=f(m,n-1)+f(m-n,n)

2.3 神奇口袋（ai 2755）

问题：给出小于40的正整数a1, a2……an，问凑出和为有多少种方法．

算法：设f(a1, a2……an, 40,)为用a1, a2……an 凑出40的方法数，考虑凑数的方法分为两类，用到a1和用不到a1,则有
f(a1，a2……an,40) = f(a1，a2，，，40-a1)+ f(a2，，，an，40)
这里考虑到在实现上函数的参数个数要统一，所以把a1, , a2……an放到一个数组中，用numbers[] 存放所有的整数，n表示数组中整数的个数，ith表示从数组中第ith个数开始凑数(ih前面的不用）表示要凑出的总数数开始凑数(ith前面的不用），sum表示要凑出的总数，则
f(numbers, n, ith, sum) =

　　　　　　　　　　 f(numbers，n，ith+1，sum-numbers[ith])//用到ith

　　　　　　　　　　　　　　+ f(numbers, n, ith+1, sum) //不用ith

2.4 八皇后问题（ai 2754）

问题：会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！（即八个皇后在排列时不能同在一行、一列或一条斜线上）这就是著名的八皇后问题
八皇后问题可用八重循环解决。但是N皇后问题呢?
算法：递归可以用来实现任意多重循环：如果有多个变量，每个变量有各自的取值范围，要覆盖这些变量值的全部组合，可以用递归实现
此题没有什么直接的递推关系，写递归就是为了起到多重循环的作用
方法1：设置8*8矩阵仿真棋盘来表示当前已经摆放好的棋子所控制的区域
方法2：用3个1维数组来记录每一列、每个45度的斜线和每个135度的斜线上是否已经被已放置的棋子控制
方法3：不设仿真棋盘，只用一个有8个元素的数组记录已经摆放的棋子放在什么位置。当要放置一个新棋子时，只需判断它与已放置的棋子间是否冲突。