递归的概念

​是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。汉诺塔问题，是常见可用递归解决的问题，不过也有非递归的解法。菲波纳契数列可用递归定义。以下为求汉诺塔问题的Pascal程序：procedure Hanoi(n:integer;x,y,z:char);递归beginif n<>1 then beginHanoi(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. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。