【www.shanpow.com--热门范文】
(1) [递归方法]递归的两种方式
大家都知道中枢的定义，三个连续次级别走势类型重合的部分。但是自从一个叫线段的家伙横空出世后，关系就变得复杂了，三个线段重合也叫中枢了，老子还是那个老子，儿子却变成了隔壁老王的儿子。
要想把这个关系搞清楚，就得从递归说起。一般的递归定义，由两部分组成，一、f1(a0)=a1；二、f2(an)=an+1；f1和f2是两组不同的函数，缠论里设定的f1就是从分型笔线段，生长出最小级别中枢—走势类型的这套程序，括号里的a0就是分型，a1就是走势类型。
f2就是三个次级别走势类型构成中枢的程序，中枢的定义从开始到最后都是没有变的，都是三个连续次级别走势类型重合的部分，只是最初这个次级别走势类型是用笔构成的，后面的是用线段构成的。把缠论术语代入到一就是f1（1F分型）=1F走势类型，那么二则为f2（1F走势类型）=5F中枢。
由上可知，线段构成中枢的情况只适用于最小级别，比如说你在一分钟上用分型笔线段中枢递归出走势类型，就是前面说的f1（a0）=a1，那切换到5分钟就无需再画线段，只要把1分钟上得出的走势类型标记出来即可，三个1分钟走势类型重叠就是5分中枢。缠师多次强调过线段，只针对最低级别，就是拿来递归用的，所以大家不要太纠结于线段的划分。
上面说的比较抽象，看之前大盘的递归，第一张是1F图，红色是一分钟线段，白色就是一分钟中枢。本来是画了笔的，发现缩小之后密密麻麻很是混乱，就把笔删掉了。下面一张是5F图，把1F图上递归好的直接抄过来就是了，三个1F的走势类型就构成5F中枢，站在5F级别角度下，永远只针对一个正完成着的同级别中枢。
这里注意走势划分的几个原则，第一必须要符合走势终完美，缠师曾经说过本ID理论最牛的地方,就是利用走势终完美,对走势进行唯一分解。第二就是在保证中枢确立的情况下，利用结合律使得走势呈现出最完美的状态。结合律，里面学问很大.
如何使用结合律消除走势的多义性，多义性和当下性又密切相关，选择一种恰当的走势分解，对把握当下的走势极为关键。
到这里，你有没有发现一个问题，如果没有，表示你对递归的一些细节还没吃透。这问题就是在一分钟上，允许中枢延伸扩展吗？允许盘整加盘整这样的连接吗？同理，在五分钟上怎么处理？当下这一秒，脑子里有没有答案，而且这答案没有任何含糊性。如果还是一团麻，那就要悬梁刺股去啃书了。
(2) [递归方法]写递归函数的正确思维方法
递归是编程中一个相对难以理解但是却又很重要的概念. 对于从命令式语言开始学习编程的程序员天生对此有理解缺陷, 而对于从类似C++这种对函数式编程范式不友好的语言开始学习编程的程序员就更加如此了.(比如我自己) 碰巧(其实不巧)最近在读这本书(这本书国内没有引进, 网上只有巨贵的亚马逊卖的原版,
我读的是网上的中文版), Paul Graham在书中讲述的如何写递归函数的部分, 让我印象深刻. 因为原书是讲Lisp的, 当然这个部分也是用Lisp作为例子描述的, 考虑到国内会看这本书的人太少,
能看懂Lisp的就更不多了, 我这里根据自己的理解, 重新整理一下. 最重要的是, 书中原来的例子太少, 太简单, 我自己提供了一些额外的, 并且更加复杂的例子. 以期对问题能有更好的理解.
什么是递归
理解递归
使用递归
递归的问题
参考
什么是递归
迭代的是人，递归的是神
–L. Peter Deutsch
简单的定义: “当函数直接或者间接调用自己时，则发生了递归.” 说起来简单, 但是理解起来复杂, 因为递归并不直观, 也不符合我们的思维习惯, 相对于递归, 我们更加容易理解迭代. 因为我们日常生活中的思维方式就是一步接一步的, 并且能够理解一件事情做了N遍这个概念. 而我们日常生活中几乎不会有递归思维的出现.
举个简单的例子, 即在C/C++中计算一个字符串的长度. 下面是传统的方式, 我们一般都这样通过迭代来计算长度, 也很好理解.
size_t length(const char *str) {
size_t length = 0;
while (*str != 0) {
++length;
++str;
}
return length;
}
而事实上, 我们也可以通过递归来完成这样的任务.
size_t length(const char *str) {
if (*str == 0) {
return 0;
}
return length(++str) + 1;
}
只不过, 我们都不这么做罢了, 虽然这样的实现有的时候可能代码更短, 但是很明显, 从思维上来说更加难以理解一些. 当然, 我是说假如你不是习惯于函数式语言的话. 这个例子相对简单, 稍微看一下还是能明白吧.
迭代的算法可以这样描述: 从第一个字符开始判断字符串的每一个字符, 当该字符不为0的时候, 该字符串的长度加一.
递归的算法可以这样描述: 当前字符串的长度等于当前字符串除了首字符后, 剩下的字符串长度+1.
作为这么简单的例子, 两种算法其实大同小异, 虽然我们习惯迭代, 但是, 也能看到, 递归的算法无论是从描述上还是实际实现上, 并不比迭代要麻烦.
理解递归
在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证. 比如, 另外一个常见的例子是阶乘的计算.
阶乘的定义: “一个正整数的阶乘（英语：factorial）是所有小于或等于该数的正整数的积，并且0的阶乘为1。” 以下是Ruby的实现:
def factorial(n)
if n <= 1 then
return 1
else
return n * factorial(n - 1)
end
end
我们怎么判断这个阶乘的递归计算是否是正确的呢? 先别说测试, 我说我们读代码的时候怎么判断呢?
回溯的思考方式是这么验证的, 比如当n = 4时, 那么factoria(4)等于4
* factoria(3), 而factoria(3)等于3
* factoria(2), factoria(2)等于2
* factoria(1), 等于2 * 1, 所以factoria(4)等于4
* 3 * 2 * 1. 这个结果正好等于阶乘4的迭代定义.
用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解.
Paul Graham提到一种方法, 给我很大启发, 该方法如下:
当n=0, 1的时候, 结果正确.
假设函数对于n是正确的, 函数对n+1结果也正确.
如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。
这种方法很像数学归纳法, 也是递归正确的思考方式, 事实上, 阶乘的递归表达方式就是1!=1，n!=(n-1)!×n(见wiki).
当程序实现符合算法描述的时候, 程序自然对了, 假如还不对, 那是算法本身错了…… 相对来说, n,n+1的情况为通用情况, 虽然比较复杂, 但是还能理解, 最重要的, 也是最容易被新手忽略的问题在于第1点, 也就是基本用例(base case)要对. 比如, 上例中, 我们去掉if
n <= 1的判断后, 代码会进入死循环, 永远不会结束.
使用递归
既然递归比迭代要难以理解, 为啥我们还需要递归呢? 从上面的例子来看, 自然意义不大, 但是很多东西的确用递归思维会更加简单……
经典的例子就是斐波那契数列, 在数学上, 斐波那契数列就是用递归来定义的:
·F0 = 0
·F1 = 1
·Fn = Fn – 1 + Fn – 2
有了递归的算法, 用程序实现实在再简单不过了:
def fibonacci(n)
if n == 0 then
return 0
elsif n == 1 then
return 1
else
return fibonacci(n - 1) + fibonacci(n - 2)
end
end
改为用迭代实现呢? 你可以试试.
上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写, 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?
Paul Graham提到, 你只需要做两件事情:
你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.
这个过程还是数学归纳法的方法, 只不过和上面提到的一个是验证, 一个是证明.
现在我们用这个方法来寻找汉诺塔这个游戏的解决方法.(这其实是数学家发明的游戏)
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
1.每次只能移动一个圆盘.
2.大盘不能叠在小盘上面.
这个游戏在只有3个盘的时候玩起来较为简单, 盘越多, 就越难, 玩进去后, 你就会进入一种不停的通过回溯来推导下一步该干什么的状态, 这是比较难的. 我记得第一次碰到这个游戏好像是在大航海时代某一代游戏里面, 当时就觉得挺有意思的. 推荐大家都实际的玩一下这个游戏, 试试你脑袋能想清楚几个盘的情况.
现在我们来应用Paul Graham的方法思考这个游戏.
一般情况:
当有N个圆盘在A上, 我们已经找到办法将其移到C杠上了, 我们怎么移动N+1个圆盘到C杠上呢? 很简单, 我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上, 然后再把第N+1个圆盘(最后一个)移动到C上, 再用同样的方法将在B杠上的N个圆盘移动到C上. 问题解决.
基本用例:
当有1个圆盘在A上, 我们直接把圆盘移动到C上即可.
算法描述大概就是上面这样了, 其实也可以看作思维的过程, 相对来说还是比较自然的. 下面是Ruby解:
def hanoi(n, from, to, other)
if n == 1 then
puts from + " -> " + to
else
hanoi(n-1, from, other, to)
hanoi(1, from, to, other)
hanoi(n-1, other, to, from)
end
end
当n=3时的输出:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
上述代码中, from, to, other的作用其实也就是提供一个杆子的替代符, 在n=1时, 其实也就相当于直接移动. 看起来这么复杂的问题, 其实用递归这么容易, 没有想到吧. 要是想用迭代来解决这个问题呢? 还是你自己试试吧, 你试的越多, 就能越体会到递归的好处.
递归的问题
当然, 这个世界上没有啥时万能的, 递归也不例外, 首先递归并不一定适用所有情况, 很多情况用迭代远远比用递归好了解, 其次, 相对来说, 递归的效率往往要低于迭代的实现, 同时, 内存好用也会更大, 虽然这个时候可以用尾递归来优化,
但是尾递归并不是一定能简单做到.
参考
Ansi Common Lisp
精通递归程序设计
writen by
九天雁翎(www.jtianling.com)
(3) [递归方法]递归算法实例讲解
题图：递归
在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。
借助递归方法，我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解，递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。但在带来便捷的同时，也会有一些缺点，也即：通常用递归方法的运行效率不高。
递归算法实例
1.Fibonacci函数
讲到递归，我们最先接触到的一个实例便是斐波那契数列。斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …特别指出：第0项是0，第1项是第一个1。这个数列从第二项开始，每一项都等于前两项之和。斐波那契数列递归法实现：
int Fib(int n)
{
if(n<1)
{
return -1;
}
if(n == 1|| n == 2)
{
return 1;
}
return Fib(n-1)+Fib(n-2);
}
2.汉诺塔问题
汉诺塔示意图
汉诺塔是根据一个传说形成的数学问题：有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。问：如何移？最少要移动多少次？
最早发明这个问题的人是法国数学家爱德华·卢卡斯。
传说印度某间寺院有三根柱子，上串64个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。若传说属实，僧侣们需要264 ? 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5849亿年才能完成。整个宇宙现在也不过137亿年。这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。佛教中确实有“浮屠”（塔）这种建筑；有些浮屠亦遵守上述规则而建。“河内塔”一名可能是由中南半岛在殖民时期传入欧洲的。
以下是汉诺塔问题的递归求解实现：
/*
* Project : hannoi
* File : main.cpp
* Author : iCoding
*
* Date & Time : Sat Oct 06 21:01:55 2012
*
*/
using namespace std;
#include <iostream>
#include <cstdio>
void hannoi (int n, char from, char buffer, char to)
{
if (n == 1)
{
cout << "Move disk " << n << " from " << from << " to " << to << endl;
}
else
{
hannoi (n-1, from, to, buffer);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hannoi (n-1, buffer, from, to);
}
}
int main()
{
int n;
cin >> n;
hannoi (n, "A", "B", "C");
return 0;
}
更详细解析请参考：编程解决汉诺塔问题
3.二叉树遍历
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
一颗简单的二叉树
二叉树的遍历分为三种：前(先)序、中序、后序遍历。
设L、D、R分别表示二叉树的左子树、根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。
假设我们有一个包含值的value和指向两个子结点的left和right的树结点结构。我们可以写出这样的过程：
先序遍历(递归实现)：
visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right
