漫谈递归思想

2024-08-24 01:32

文章标签 递归思想漫谈

本文主要是介绍漫谈递归思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文转自：http://www.cnblogs.com/BLoodMaster/archive/2010/03/23/1692641.html

漫谈递归思想

编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间，尤其对模型所描述的问题概念不清的时候，想要自己设计一个递归那么就更是有难度了。今天我也花费了半个小时来搞明白二叉树的平衡性的递归模型，首先我不明白什么叫做平衡性，所以花费的时候大部分实在试探理解平衡性的含义。在搞明白的时候，我突然想到假如让我来设计，在我知道平衡性的前提下，我是否可以建立如此简洁的递归模型。为此，我遇到的问题是我们到底在什么情况下适用递归模型，并且递归模型如何建立。
数学都不差的我们，第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。（当然如果对于问题很清楚的人也可以直接简历递归模型了，运用数模做中介的是针对对于那些问题还不是很清楚的人），自己观察递归，我们会发现，递归的数学模型其实就是归纳法，这个在高中的数列里面是最常用的了。

回忆一下归纳法：

归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。

如果运用列表来形容归纳法就是：

步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再是用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。
这样其实就结束了，递归也就出来了。

递归算法的一般形式：

void func( mode)
{ if(endCondition){ constExpression //基本项 } else{accumrateExpreesion //归纳项mode = expression //步进表达式func(mode) //调用本身，递归}
}

最典型的就是N！算法，这个最具有说服力。理解了递归的思想以及使用场景，基本就能自己设计了，当然要想和其他算法结合起来使用，还需要不断实践与总结了。

例如：返回一个二叉树的深度：

int depth(Tree t)
{ if(!t) return 0; else { int a = depth(t.right); int b = depth(t.left); return (a>b)?(a+1):(b+1); } 
}

判断一个二叉树是否平衡：

int isB(Tree t)
{ if(!t) <span style="white-space:pre">	</span>return 0; int left = isB(t.left); int right = isB(t.right); if(left>=0&&right>=0&&left-right<=1||left -right>=-1) return (left<right)?(right +1):(left + 1); else return -1; 
}

上面这两个递归的难易程度就不一样了，第一个关于深度的递归估计只要了解递归思想的都可以短时间设计出来，但第二个估计就要长点时间了。纯递归问题的难易主要纠结于一些条件表达式的构造以及初值的设置（上面的为直接表达式值的设定）。

最后需要补充的是，很多不理解递归的人（今天在csdn里面看到一个初学者的留言），总认为递归完全没必要，用循环就可以实现，其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环，大家都知道递归分两步，递和归，那么可以知道递归对于空间性能来说，简直就是造孽，这对于追求时空完美的人来说，简直无法接接受，如果递归仅仅是循环，估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体，也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列，字符串长度不定，那么如果你用循环来实现，你会发现你根本写不出来，这个时候就要调用递归，而且在递归模型里面还可以使用分支递归，例如for循环与递归嵌套，或者这节枚举几个递归步进表达式，每一个形成一个递归。

这篇关于漫谈递归思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！