A. 递归的概念
是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。
汉诺塔问题，是常见可用递归解决的问题，不过也有非递归的解法。
菲波纳契数列可用递归定义。
以下为求汉诺塔问题的Pascal程序：
procere Hanoi(n:integer;x,y,z:char);
递归
begin
if n<>1 then begin
Hanoi(n-1,x,z,y);
writeln(x,n,z);
Hanoi(n-1,y,x,z);
else writeln(x,n,z);
end;
end;
上述程序用接近自然语言的伪代码可表述如下：
Hanoi 过程 (整型参数n; 字符型参数 x,y,z);
//注：n 代表本步中要处理的盘子数，x,y,z 分别表示 n 号盘子原来所在柱子、经由柱子、目标柱子
开始
如果 n 不为 1 ，那么：开始
调用 Hanoi 过程 (参数为 n-1,x,z,y);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 x 经由柱子 z 移动到柱子 y
输出 x,n,z; //注：表示将 n 号盘子从 x 移动到 z
调用 Hanoi 过程 (参数为 n-1,y,x,z);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 y 经由柱子 x 移动到柱子 z
结束; //以上程序段就完成了把 n 个盘子从柱子 x 经由柱子 y 移动到柱子 z
否则 输出 x,n,z; //注：若 n 为1 的话本句直接输出表示将 n 号盘子从 x 移动到 z
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
函数嵌套调用过程示例
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
B. 算法的子集和数问题
回溯算法设计2008-05-29 10:15 P.M.[实验目的]
1. 掌握回溯法解题的基本思想；
2. 掌握回溯算法的设计方法；
3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。
[预习要求]
1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；
2. 了解子集和数问题及解向量的定长和变长状态空间表示；
3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；
4. 分析深度优先扩展状态空间树节点或回溯的条件；
5. 分析和设计生成解向量各分量可选值的实现方法；
6. 设计和编制回溯算法的递归和迭代程序。
[参考数据类型或变量]
float s; // 表示有可能抵达答案节点的子路径上的元素之和；
float r; // 尚未测试的剩余集合元素之和；
float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化；
int x[n]; // 定长表示的解向量, 各元素初始值为0；
[参考子程序接口与功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 针对问题实例的递归回溯算法。
void IterativeSubset(int m)
功能: 针对问题实例的迭代回溯算法。
void InitializeInstanse(void)
功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。
[实验步骤]
1. 录入、修改并测试你的程序，直至正确为止；
2. 针对问题实例，实录运行时的输入、输出界面；
3. 将你的程序和实录的界面存盘备用。
[实验报告要求]
1. 阐述实验目的和实验内容；
2. 提交模块化的实验程序源代码；
3. 简述程序的测试过程，提交实录的输入、输出界面；
4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。
[思考与练习]
1. 试针对解向量的变长表示设计回溯算法，上机测试正确性。
2. 试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。
#include<stdio.h>
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和；*/
float r; /*尚未测试的剩余集合元素之和；*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化；*/
int x[n]; /*定长表示的解向量, 各元素初始值为0；*/
int M;
int k;
void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}
else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");
C. 递归主方法
递归的主要方法是什么？
一、递归算法
递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。
二、递归程序
在支持自调的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：
这一程序在Scheme语言中可以写作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不动点组合子
即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。
尾部递归
尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能够解决的问题
数据的定义是按递归定义的。如Fibonacci函数。
问题解法按递归算法实现。如Hanoi问题。
数据的结构形式是按递归定义的。如二叉树、广义表等。
四、递归数据
数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
这一定义相当于宣告“一个链表或是空串行，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。
D. python-027-递归-求序列最大值、计算第n个调和数、转换字符到整数
递归，emmmmmmm，拥有一种魅力，接近人的立即思维，容易理解，又不容易理解。
递归算法的优点： 它使我们能够简洁地利用重复结构呈现诸多问题。通过使算法描述以递归的方式利用重复结构，我们经常可以避开复杂的案例分析和嵌套循环。这种算法会得出可读性更强的算法描述，而且十分有效。
但是 ，递归的使用要根据相应的成本来看，每次递归python解释器都会给一个空间来记录函数活动状态。但是有时候内存成本很高，有时候将递归算法转为非递归算法是一种好办法。
当然我们可以换解释器、使用堆栈数据结构等方法，来管理递归的自身嵌套，减小储存的活动信息，来减小内存消耗。
最近算法学到了递归这一块，写了三个课后习题：
给一个序列S，其中包含n个元素，用递归查找其最大值。
输出：
调和数：Hn = 1 + 1/2 + 1/3 + ··· + 1/n
输出：
例如："12345"<class 'str'> 转换为12345<class 'int'>
输出：
递归分为线性递归、二路递归、多路递归。