一. 递归的定义
第一部分称为基例,列出了产生集合中其他元素的基本元素。
第二部分给出由基本元素或已有对象产生新对象的构造规则。
例如要构造自然数集合,取0为基本元素,然后给出累加1的操作即可。
二. 递归的要点
在运用递归的时候,一定不要忘记了递归的终止条件,所谓递归,递归,归去来兮,否则就会永远递归下去。
在递归时,我们经常说是自己调用自己,其实是一个函数调用同一个函数的另外一个实例。
递归操作虽然清晰明了,但是它会消耗更多的内存,更多的时间。
三. 递归的分类
尾递归:函数的末尾只使用一个递归的调用
非尾递归
四. 利用递归实现回溯算法应用于八皇后问题
回溯算法思想:走一步,看一步,不行的话,退回到上一步,另辟蹊径。
#include<iostream> using namespace std; class ChessBoard { private: int map[9][9]; int count = 0; int sum = 0; public: void inits(); bool check(int, int); void putChess(int); void print(); }; void ChessBoard::inits() { for (int i = 1; i < 9; i++) for (int j = 1; j < 9; j++) { map[i][j] = 0; } } bool ChessBoard::check(int x, int y) { int a=x, b=y; for (int j = 1; j < 9; j++) { if (map[x][j] == 1 || map[j][y] == 1) return false; a = x + j; b = y + j; if (map[a][b] == 1 && a <= 8 && b <= 8) return false; a = x - j; b = y - j; if (map[a][b] == 1 && a >= 1 && b >= 1) return false; a = x - j; b = y + j; if (map[a][b] == 1 && a >= 1 && b <=8) return false; a = x + j; b = y - j; if (map[a][b] == 1 && a <= 8 && b >=1) return false; } return true; } void ChessBoard::putChess(int n) { if (n > 8 && count == 8) { sum += 1; print(); return; } if (n > 8) return; for (int i = 1; i < 9; i++) { if (check(n, i)) { map[n][i] = 1; count += 1; putChess(n + 1); map[n][i] = 0; count -= 1; } } } void ChessBoard::print() { for (int i = 1; i < 9; i++) { for (int j = 1; j < 9; j++) { cout << map[i][j] << " "; } cout << endl; } cout << endl << endl; cout << sum; } int main(void) { ChessBoard a; a.inits(); a.putChess(1); return 0; }
Thank for your reading!!!
公众号:FPGA之旅