理论上讲，仅仅是理论！任何递归算法都有其非递归算法，但实际运用中，能够写出相应的非递归算法并加以实现的递归算法是很少的，所以递归仍是解决复杂问题的常用方法之一。
您的举报已经提交成功，我们将尽快处理，谢谢！
一个函数直接或间接调用自己就叫做递归
对一个问题的求解可以转换为一个规模较小的原来问题的求解时。要用到递归算法，最简单的例子：阶乘问题
n!=n*(n-1)...
(1) 不太可能吧
b)改进递归外的部分
大家还关注
='a'&&c'Z'&&c麻烦大家帮我选一下!
将小写字母变成对...
(window.slotbydup=window.slotbydup || []).push({
id: '2081942',
container: s,
size: '1000,60',
display: 'inlay-fix'推荐这篇日记的豆列
······用归纳法来理解递归
服务器君一共花费了144.848 ms进行了4次数据库查询，努力地为您提供了这个页面。
试试阅读模式？希望听取您的建议
为什么要用递归
编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间，尤其对模型所描述的问题概念不清的时候，想要自己设计一个递归那么就更是有难度了。
很多不理解递归的人（今天在csdn里面看到一个初学者的留言），总认为递归完全没必要，用循环就可以实现，其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环，大家都知道递归分两步，递和归，那么可以知道递归对于空间性能来说，简直就是造孽，这对于追求时空完美的人来说，简直无法接接受，如果递归仅仅是循环，估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体，也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列，字符串长度不定，那么如果你用循环来实现，你会发现你根本写不出来，这个时候就要调用递归，而且在递归模型里面还可以使用分支递归，例如for循环与递归嵌套，或者这节枚举几个递归步进表达式，每一个形成一个递归。
用归纳法来理解递归
数学都不差的我们，第一反应就是在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。 （当然如果对于问题很清楚的人也可以直接简历递归模型了，运用数模做中介的是针对对于那些问题还不是很清楚的人）
自己观察递归，我们会发现，递归的数学模型其实就是归纳法，这个在高中的数列里面是最常用的了。回忆一下归纳法。
适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是：
步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再是用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。
这样其实就结束了，递归也就出来了。递归算法的一般形式：
void func( mode)
if(endCondition)
constExpression
accumrateExpreesion
mode=expression
//步进表达式
func(mode)
//调用本身，递归
最典型的就是N!算法，这个最具有说服力。理解了递归的思想以及使用场景，基本就能自己设计了，当然要想和其他算法结合起来使用，还需要不断实践与总结了。
#include "stdio.h"
#include "math.h"
int main(void)
printf("请输入需要计算阶乘的数n：");
scanf("%d",&n);
rs = factorial(n);
printf("%d ", rs);
// 递归计算过程
int factorial(n){
if(n == 1) {
return n * factorial(n-1);
求阶乘的递归比较简单，这里就不展开了。
再来两个递归的例子
返回一个二叉树的深度：
int depth(Tree t){
if(!t) return 0;
int a=depth(t.right);
int b=depth(t.left);
return (a>b)?(a+1):(b+1);
判断一个二叉树是否平衡：
int isB(Tree t){
if(!t) return 0;
int left=isB(t.left);
int right=isB(t.right);
if( left >=0 && right >=0 && left - right =-1)
return (left < right)? (right +1) : (left + 1);
else return -1;
第一个算法还是比较好理解的，但第二个就不那么好理解了。第一个算法的思想是：如果这个树是空，则返回0；否则先求左边树的深度，再求右边数的深度，然后对这两个值进行比较哪个大就取哪个值+1。而第二个算法，首先应该明白isB函数的功能，它对于空树返回0，对于平衡树返回树的深度，对于不平衡树返回-1。明白了函数的功能再看代码就明白多了，只要有一个函数返回了-1，则整个函数就会返回-1。（具体过程只要认真看下就明白了）
对于递归，最好的理解方式便是从函数的功能意义的层面来理解。了解一个问题如何被分解为它的子问题，这样对于递归函数代码也就理解了。这里有一个误区（我也曾深陷其中），就是通过分析堆栈，分析一个一个函数的调用过程、输出结果来分析递归的算法。这是十分要不得的，这样只会把自己弄晕，其实递归本质上也是函数的调用，调用的函数是自己或者不是自己其实没什么区别。在函数调用时总会把一些临时信息保存到堆栈，堆栈只是为了函数能正确的返回，仅此而已。我们只要知道递归会导致大量的函数调用，大量的堆栈操作就可以了。
递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。
延伸阅读此文章所在专题列表如下：
本文地址：，欢迎访问原出处。
不打个分吗？
转载随意，但请带上本文地址：
如果你认为这篇文章值得更多人阅读，欢迎使用下面的分享功能。
小提示：您可以按快捷键 Ctrl + D，或点此 。
大家都在看
现代魔法研究协会欢迎你
阅读一百本计算机著作吧，少年
Joel Spolsky (作者), 阮一峰 (译者)
《软件随想录:程序员部落酋长Joel谈软件》是一部关于软件技术、人才、创业和企业管理的随想文集，作者以诙谐幽默的笔触将自己在软件行业的亲身感悟娓娓道来，观点新颖独特，内容简洁实用。全书分为 36讲，每一讲都是一个独立的专题。《软件随想录:程序员部落酋长Joel谈软件》从不同侧面满足了软件开发人员、设计人员、管理人员及从事软件相关工作的人员的学习与工作需要。
扫一扫，在手机上阅读
栏目最新博文
15,330 views
10,485 views
10,575 views
10,706 views
10,778 views
12,082 views
7,741 views
7,431 views
9,451 views
9,196 views
栏目博文推荐
5,001 views
12,082 views
8,959 views
10,706 views
5,713 views
3,593 views
9,451 views
8,129 views
2,656 views
4,509 views
帮助别人，就是帮助自己。
1,025 views
关于网站与作者
互联网信息太多太杂，各互联网公司不断推送娱乐花边新闻，SNS，微博不断转移我们的注意力。但是，我们的时间和精力却是有限的。这里是互联网浩瀚的海洋中的一座宁静与美丽的小岛，供开发者歇息与静心潜心修炼（愿景）。
“Veda”的本义是知识、启示，希望这里能为开发者提供充足的技术资料。
我的电子邮件gonnsai(，腾讯微博：，欢迎与我联系。下面是我统计的几种方案：
第一种方案(递归式): 简单的表结构为： CategoryID int(4), CategoryName nvarchar(50), ParentID int(4), Depth int(4) 这样根据ParentID一级级
下面是我统计的几种方案： 第一种方案(递归式): 简单的表结构为： CategoryID int(4), CategoryName nvarchar(50), ParentID int(4), Depth int(4) 这样根据ParentID一级级的运用递归找他的上级目录。 还有可以为了方便添加CategoryLeft,CategoryRight保存他的上级目录或下级目录 第二种方案： 设置一个varchar类型的CategoryPath字段来保存目录的完整路径，将父目录id用符号分隔开来。比如：1,5,8,10 第三种方案： 每级分类递增两位数字的方法 示例： 一级分类：01,02,03,04... 二级分类：03,0104... 三级分类：102,010103... 分析一下，其实第三种方案并不能真正意义上做无限级的分类，而第二种方案，虽然比较容易得到各上级及下级的分类信息。但，添加和转移分类的时候操作将很麻烦。 而且，也完全违反了数据库设计范式。 其实我也一直在用第二种方案的。为了查找方便，我有时都在新闻表里加上CategoryID和CategoryPath 而我今天要说的算法其实是第二种方案的改进版，一般做分类都是使用一个表格来保存分类信息。 而我这里，要新建两个表格，一个表格是保存分类信息表，一个保存分类关系表。 表结构如下： 表1：tomi_Category CategoryID int(4), '编号 CategoryName nvarchar(50), '分类名称 Depth int(4), '深度 表2：tomi_CategoryBind CategoryID int(4), BindCategoryID int(4), Depth int(4), 添加，编辑，删除操作有点麻烦。。我是直接用存储过程的。。不知道大家能看得懂不。。哈哈。 1、添加分类(Category_Add) 复制代码 代码如下: CREATE proc [dbo].[Category_Add] @CategoryName nvarchar(50), @BindCategoryID int, @CategoryID int output as declare @Success bit set @Success=1 --生成不重复的CategoryID declare @i bit set @i=0 while @i=0 begin set @CategoryID=LEFT( + CONVERT(bigint, ABS(CHECKSUM(NEWID()))), 8) if(not exists(select CategoryID from tomi_Category where CategoryID=@CategoryID)) set @i=1 end --得到depth declare @depth int set @depth=0 select @depth=depth from tomi_Category where CategoryID=@BindCategoryID set @depth=@depth+1 --插入 BEGIN TRAN insert into tomi_Category(categoryID,CategoryName,Depth) values(@CategoryID,@CategoryName,@Depth) if(@@ERROR&&0) BEGIN ROLLBACK TRAN set @Success=0 END insert into tomi_CategoryBind(CategoryID,BindCategoryID,Depth) values(@CategoryID,@CategoryID,@Depth) if(@@ERROR&&0) BEGIN ROLLBACK TRAN set @Success=0 END insert into tomi_CategoryBind(CategoryID,BindCategoryID,Depth) select @CategoryID,BindCategoryID,Depth from tomi_CategoryBind where CategoryID=@BindCategoryID if(@@ERROR&&0) BEGIN ROLLBACK TRAN set @Success=0 END COMMIT TRAN print @CategoryID
每个分类在tomi_CategoryBind有完整的目录结构。。一个分类在tomi_CategoryBind的记录数等于他在tomi_Category的depth值。 图片： 2、编辑修改分类(Category_Edit) 复制代码 代码如下: CREATE proc [dbo].[Category_Edit] @CategoryID int, @CategoryName nvarchar(50), @BindCategoryID int as --更新 BEGIN TRAN update tomi_Category set CategoryName=@CategoryName where CategoryID=@CategoryID IF @@ERROR&&0 BEGIN ROLLBACK TRAN return 0 END COMMIT TRAN --检测是否更改了上级目录 declare @is bit set @is=0 if(exists(select CategoryID from tomi_CategoryBind where CategoryID=@CategoryID and BindCategoryID=@BindCategoryID and Depth=(select Depth-1 from tomi_Category where CategoryID=@CategoryID))) set @is=1 print @is --更改了深度 if(@is=0) BEGIN --得到上级目录的depth declare @depth int set @depth=0 select @depth=depth from tomi_Category where CategoryID=@BindCategoryID set @depth=@depth+1 --print @depth --更改子目录 declare @i int declare @sCategoryID int declare @sBindCategoryID int declare @tCategoryIDList Table ( CategoryID int, FlagID tinyint ) insert @tCategoryIDList select c.CategoryID,0 from tomi_Category c left join tomi_CategoryBind b on c.CategoryID=b.CategoryID where b.BindCategoryID=@CategoryID order by c.Depth set @i=1 set @sBindCategoryID=@BindCategoryID declare @errs int set @errs=0 BEGIN TRAN while(@i&=1) BEGIN select @sCategoryID=0 select Top 1 @sCategoryID=CategoryID from @tCategoryIDList where FlagID=0 set @i=@@RowCount --print @sCategoryID if @sCategoryID&0 BEGIN --删除，更新 delete from tomi_CategoryBind where CategoryID=@sCategoryID set @errs=@errs+@@error update tomi_Category set depth=@depth where CategoryID=@sCategoryID set @errs=@errs+@@error --插入 insert into tomi_CategoryBind(CategoryID,BindCategoryID,Depth) values(@sCategoryID,@sCategoryID,@Depth) set @errs=@errs+@@error insert into tomi_CategoryBind(CategoryID,BindCategoryID,Depth) select @sCategoryID,BindCategoryID,Depth from tomi_CategoryBind where CategoryID=@sBindCategoryID set @errs=@errs+@@error set @sBindCategoryID=@sCategoryID set @Depth=@Depth+1 --print @sCategoryID --print @sBindCategoryID --print @Depth --print '--' END update @tCategoryIDList set FlagID=1 where CategoryID=@sCategoryID END if(@errs&0) BEGIN ROLLBACK TRAN return 0 END else COMMIT TRAN END
3、删除分类(Category_Del) 会直接删除子分类 复制代码 代码如下: create proc Category_Del @CategoryID int as BEGIN TRAN delete from tomi_Category where CategoryID in (select CategoryID from tomi_CategoryBind where CategoryID=@CategoryID or BindCategoryID=@CategoryID) if(@@ERROR&&0) BEGIN ROLLBACK TRAN return 0 END delete from tomi_CategoryBind where CategoryID in (select CategoryID from tomi_CategoryBind where CategoryID=@CategoryID or BindCategoryID=@CategoryID) if(@@ERROR&&0) BEGIN ROLLBACK TRAN return 0 END COMMIT TRAN
4、分类列表，显示分类(Category_List) 复制代码 代码如下: CREATE proc Category_List as select c.* from tomi_Category c left join tomi_CategoryBind b on c.CategoryID=b.CategoryID where b.Depth=1 order by b.BindCategoryID,c.Depth GO
exec Category_List 可以直接让分类等级查询出来。而且显示全部的话，一次查询即可，只需判断depth就行。 图片： 5、上级子分类列表 (Category_upTree) 复制代码 代码如下: Create Proc Category_UpTree @CategoryID int as select c.* from tomi_Category c left join tomi_CategoryBind b on c.CategoryID=b.BindCategoryID where b.CategoryID=@CategoryID order by c.Depth GO
exec Category_UpTree
这样就可以得到一个分类的完整子目录集，方便吧，只要一条sql. 图片： 6、下级子分类列表(Category_downTree) 复制代码 代码如下: Create Proc Category_DownTree @CategoryID int as select c.* from tomi_Category c left join tomi_CategoryBind b on c.CategoryID=b.CategoryID where b.BindCategoryID=@CategoryID order by c.Depth GO
exec Category_DownTree
这样可以得到一个分类完整下级目录。比如得到某个分类和其分类的子分类下的所有产品用这个就好。。方便，一条sql. 图片： 以上是初稿，只是随意的测试了几次。。。有错误的，还请大家指出。。 呵呵。转载请注明链接，博客园首发，多谢。 作者：TomiWong 时间：