1  //求a和b的最大公约数2     int GCD(int a, int b)3     {4         if (a % b == 0)5             return b;6         else 7            return GCD(b, a % b);8     }

1 string reverseString(string str)2     {3         if (str.length() == 0) 4             return "";5         else6             return reverseString(str.substr(1)) + str[0];7     }

 //折半求幂， 效率提高    int Raise(int base, int exp)    {        if (exp == 0)            return 1;        else {            int half = Raise(base, exp / 2);            if (exp % 2 == 0)   //奇偶情况不同                return half * half;            else                 return base * half * half;        }    } 

1 //递归判断是否为回文，比较相等且剩余的字串为回文则是回文2     bool isPalindrome(string s) 3     {4         if (s.lenth() <= 1)5             return true;6         else 7             return s[0] == s[s.length() - 1] && 8                     isPalindrome(s.substr(1, s.length() - 2));9     }      

 //二分查找的递归实现    int BSearch(Vector<string> &v, int start, int end, string key)    {        if (start > end)            return false;        int mid = (start + end) / 2;        if (v[mid] == key)            return mid;        else if (v[mid] < key)            return BSearch(v, mid + 1, end, key);        else             return BSearch(v, start, mid - 1, key);    }

 //N个数中找出K个数有多少种方法    int CNK(int n, int k)    {        if (k == 0 || k == n)            retrun 1;        else             return CNK(n - 1, k) + CNK(n - 1, k - 1);     }    //将第k个数单独拿出来，那么找出k个数就有两种情况：包含k和不包含k。    //包含k需要在n - 1中找出k - 1个数，有CNK（n - 1，k - 1）种情况；    //不包含k需要在n - 1中找出k个数     //两种情况相加即为总共的情况

 1 void DrawFractal(double x, double y, double width, double height) 2     { 3         DrawTraingle(x, y, width, height); 4         if (width < 0.2 || height < 0.2) { 5             return; 6         } 7         double halfWidth = width / 2; 8         double halfHeight = height / 2; 9         DrawFractal(x, y, halfWidth, halfHeight);10         DrawFractal(x + halfWidth, y, halfWidth, halfHeight);11         DrawFractal(x + halfWidth / 2, y + halfHeight, halfWidth, halfHeight);12     }

 1 void DrawMondrian(double x, doouble y, double w, double h) 2     { 3         if (w < 1 || y < 1) 4             return; 5         Fillrectangle(x, y, w, h, RandomColor()); 6         switch(RandomInteger(0, 2)) { 7             case 0: 8                 break; 9             case 1:10                 double midX = RandomReal(0, w);11                 DrawBlackLine(x + midX, y, h);12                 DrawMondrian(x, y, midX, h);13                 DrawMondrian(midX, y, w - midX, h);14                 break;15             case 2:16                 double midY = Random(0, h);17                 DrawBlackLine(x, y + midY, w);18                 DrawMondrian(x, y, w, midY);19                 DrawMondrian(x, y + midY, w, h - midY);20                 break;21         }22     }

1 //汉诺塔，将n个塔从src移动到dst上，tmp为临时借用2     MoveTower(int n, char src, char dst, char tmp)3     {4         if (n > 0) {5             MoveTower(n - 1, src, tmp, dst);  //只需要将n-1个从src移动到tmp上，借助dst6             MoveStringDisk(src, dst);   //将第n个从src移动到dst上，只需要一步；7             MoveTower(n - 1, tmp, dst, src);    //再将n-1个从tmp上移动到dst上，借助src；8         }9     }

 1  //全排列，如：将字符串“ABCD”中出现的字符不同的组合全部输出 2     //soFar表示已经排列好的字符串，rest表示还需要继续排列的字符串 3     void RecPermute(string soFar, string rest)  4     { 5         //如果rest为空，即所有字符排列完毕，输出soFar 6         if (rest == "") {        7             cout << soFar << endl; 8         } else { 9             //循环将rest中的每个字符轮流当成已排列好的字符10             for (int i = 0; i < rest.lenth(); i++) {11                 string next = soFar + rest[i];   //next表示下次递归的soFar字符串12                 string remain = rest.substr(0, i) + rest.substr(i + 1); //remain表示除去i本身后剩余的字符串，表示下次递归没有排列的字符串13                 RecPermute(next, remain);14             }15         }16     }17     //调用函数，空字符串“”为已排列好的字符串，s为待排列的字符串18     void ListPermutations(String s)19     {20         RecPermute("", s);21     }22     //如果输入内容重复的字符串，会出现重复，有两种方法可以解决：1.输出到set中排除相同字母的组合；2.在生成remain时跳过重复的元素

 1   //求子集，思路为找出字符串包含第一个字符的所有子集，和不包含第一个字符的所有子集，递归 2     //至rest为空即为所有子集。类似于在N个数中找出K个数。 3     void recSubsets(string soFar, string rest) 4     { 5         if (rest == "")     //rest为空为结束条件 6             cout << soFar << endl; 7         else {              //包含第一个字符的所有子集 8             recSubsets(soFar + rest[0], rest.substr(1)); 9             recSubsets(soFar, rest.substr(1));      //不包含第一个元素的所有子集10         }11     }12     void ListSubsets(string str)   //封装13     {14         recSubsets("", str)15     }

//伪代码bool Solve(configuration conf)    {        if (no more choices)  //BASE CASE            return (conf is goal state);        for (all available choices) {            try one choice c;   //solve from here, if works out, you are done            if (Solve(conf with choice c made)) return true;            umake choice c;        }        return false;   //tried all choices, no soln found    }

 1   //在字典lex中找出是否存在字符串rest任一种排列的存在 2     bool isAnagram(string sofar, string rest, Lextion &lex) 3     { 4         if (rest == "") { 5             return lex.containsWord(soFar);     //rest为空，返回字典是否包含soFar 6         } else {            //在字典中进行rest的全排列查找 7             for (int i = 0; i < rest.length(); i++) { 8                 if (isAnagram(soFar + rest.[i],  9                     rest.substr(0, i) + rest.substr(1), lex) {10                         return true;    //如果找到，则递归调用全部返回true11                     }12             }13         }14         return false;  //所有可能性都找不到，则返回failse15     } 

 1   //Place N queens on the board without no theatened 2     //N * N的网格中放入N个皇后，且互相没有威胁。（皇后行、列、斜线可以任意行动） 3     //以列为基础，尝试所有行的可能性 4     bool Solve(Grid<bool> &board, int col) 5     { 6         if (col >= board.numCols()) //递归至列大于网格的列数，则表明所有皇后都完成 7             return true; 8         else {      //在每一列的所有行尝试放下皇后 9             for (int rowToTry; rowToTry < board.numRows(); rowToTry++) {10                 placeQueen(board, rowToTry, col);   //假设没威胁则放下皇后11                 if (Slove(board, col + 1))  //继续下一列继续递归12                     return true;13                 removeQueens(board, rowToTry, col);  //如果下一列无法放置，则回溯14             }15         }16         return failse;  //进行至此说明所有可能性都不满足，返回false17     }

 //Arrange 1 to 9 with no repeat in row, col, or block    bool solveSudoku(Grid<int> &grid)    {   //按顺序查找空位，如果找不到空位，说明已经全部填满，返回true        if (!findUnassignedLocation(grid, row, col))            return true;        else {  //在找到的空位中尝试放入1——9            for (int num = 1; num <= 9; num++) {                if (noConflicts(grid, row, col, num)) {                    grid(row, col) = num;                    if (solveSudoku(grid))  //如果可以放置，则继续递归                        return true;                    grid(row, col) = UNASSIGNED;    //如果不能放置，则回溯                }            }        }        return failse;  //进行至此则说明失败    }

 1  //Dumb solve 2     bool dumbSolve(Pazzle pazzle, string lettersToAssign) 3     { 4         if (lettersToAssigned == "") 5             rerurn pazzleSolved(pazzle); 6         else { 7             for (int num = 0; num <= 9; num++) { 8                 if (assigned(lettersToAssign, num)) { 9                     if (dumbSolve(pazzle, lettersToAssign.substr(1)))10                         return true;11                     unAssigenLetter(lettersToAssign, num);12                 }13             }14        }15        return failse;16     }