1、主方法求解递归式

一种求解大部分递归式的公式。给出递归式: T(n) = a T(n/b) + f(n) ，其中a>=1，b>1，f(n)是给定的函数，T(n)是定义在非负整数上的递归式。

2、递归树求解

用主方法求解不了的递归式，我们可以用递归树来猜测解的上界，然后用代入法来证明解的正确性。递归树的求解精确度取决于画递归树的精确度。

3、代入法

比如我们求解，递归式T(n) = 2T(n/2)+n，我们猜测解是O(nlgn)，我们要寻找到一个常数c，使得T(n)<=cnlgn。

即T(n) <= 2c(n/2)lg(n/2)+n <= cnlgn-cnlg2+n = cnlgn-cn+n

只要c>=1，T(n)<=cnlgn，所以我们的猜测是正确的。

要注意的是，代入法全凭经验，通常用递归树来确定上界，然后用代入法再证明。

扩展资料：

设p0，p1，…，pn，…是一个序列。如果pn和序列中在它前面的若干项联系起来的一个关系式对所有大于等于某个整数n0的整数n都是有效的，则称这个关系式为递归关系(recursive relation)式。

如：设(a0，a1，，ar，)是一个序列，把该序列中的ar和它前面的几个ai(0≤i<r)关联起来的方程称做一个递归关系。如关系式:ar=3ar-1 (r≥1)和错排数:Dn=(n-1)(Dn-1+Dn-2) (n=3，4，)，都是递归关系。

非线性结构的数据元素之间是一个结点元素可能对应多个直接前驱和多个后驱。一对多关系 、多对多关系、多对一关系 、一对一关系。最主要的非线性结构是树结构和图结构。

树结构是结点之间有分支、层次关系的结构，在客观世界中，树结构是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树是一个或多个结点元素组成的有限集合T，且满足如下条件：（1）有一个特定的结点元素，称为根结点Root；  （2）其余结点元素分成m个（m＞0）互不相交的有限集T1，T2，…，Tm，其中每个集又都是一棵树，这些树称为Root的子树。在树中，一个结点元素常简称结点，采用递归方式定义树结构，揭示出树的固有特性。实际上，树中的每个结点都是该树中某一子树的根。

图是另一种重要的、比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系，而同一层的结点之间没有任何横向联系。但在图中，结点之间的联系是任意的，每个结点都可以与其他的结点相联系。图的应用范围非常广泛，诸如电网络分析、交通、管道线路、集成电路布线图、工程进度安排等实际问题的处理都可以归纳为图的问题。

一规范了我从哪里来，我到哪里去

家之有谱，犹国之有史，家谱承载了国人的传统信仰，忠孝理念和行为规范，家谱里都有姓氏源流，支派迁徒，世系繁衍，人口变迁等内容。解决了我从哪里来，我是谁，我到哪里去，这些重大问题，是中华优秀传统文化的重要载体。家谱是记载同宗共组的血缘集团，世系人物和事迹等方面情况的历史图集，它与方志，正史构成了中华民族历史大厦的三大支柱，是我国珍贵文化遗产的一部分，对开展学术研究有重要价值，同时，对海内外华人寻根认祖，增强民族自心力和凝聚力也有着重要意义。

二子女家庭教育需要修谱

人生最大的成功就是子女超越自己，人生最大的失败就是一代不如一代，任何的成功都无法弥补教育的失败，每个家庭都希望子女成才，青出于蓝而胜于蓝，我们中华民族是有着五千年的文明发展史的古老民族，撰国史，编方志，修家谱是我们中华民族的优良传统文化，国有史，方有志，家有谱，家谱是中华民族的三大历史文献之一。没有家谱的家庭，如断梗浮萍，无法感知世代传承的家族力量。没有收藏家谱的家庭，缺乏孝文化教育的工具，没有家规的家庭缺乏做人做事的规矩，没有家训的家庭缺乏教育子女的标准。所谓刀有刀谱，琴有琴谱，棋有棋谱，书有书谱，画有画谱，家有家谱······有谱家庭才能实现做人靠谱，做事靠谱，说话靠谱，工作靠谱，学习靠谱，生活靠谱，婚姻靠谱，事业靠谱，人生靠谱······才能实现家庭子女，人才辈出，才能实现家族子孙人物井喷。

三实现幸福家庭，需要修谱

众所周知，百善孝为先《弟子规》曰，首孝悌，次谨信，泛爱众，而亲仁，有余力，则学文。孔子曰：今之孝者是谓能养，至于犬马皆能有养，不敬，何以别乎？明代开国皇帝朱元璋在建国初期即颁布著名“圣谕六言”孝顺父母，尊敬长上，和睦乡里，教训子孙，各安生理，毋作非为。孝是我们中华民族传统文化提倡的行为，修谱即是行孝，故民间由传说三十年不修谱视为不孝，六十年不修谱视为大不孝，九十年不修谱视为家族中严重缺乏孝文化教育。孝文化是保障家庭幸福的根本，古人云，人生有五大灾难——天灾，人祸，盗贼，官符，不孝子孙，由此可见家庭出现不孝子孙是何等的不幸，因为不孝则不和，不和则贫穷，贫穷则无知，无知导致家庭衰落乃至灭亡，很多事实证明不孝是无数家庭不幸福的来源，因此实现幸福家庭必须修家谱，守家规，遵家训，树家风，铸家魂。

四延续家业兴旺需要修谱

俗话说富不过三代，其实我们身边的很多家庭往往是富不过三十年甚至富不过三年，古人云，由家谱的家庭属于耕读靠谱家庭，有收藏家谱的家庭属于名门望族之家，有家谱有家规的家庭属于书香门第之家，有家谱有家规有家训的家庭属于豪门贵族家庭，有家谱有家规有家训有家风的家庭属于帝王将相之家，没有家谱没有家规没有家训没有家风的家庭，就缺乏延续家业兴旺的环境。

五为了家族团结需要修谱

家谱文化是中华优秀传统文化的重要组成部分，它即是凝聚族人的精神纽带，又是增进民生福祉的文化因素，纵观历史，唯有家族历史长存，生生不息，只有一个个家族的存在和延续，才有整个民族的存在和延续。家是最小国，国是最大家，只有一个个家族的小团结才能构成整个民族的大团结，有国必有史，有家必有谱，家谱是一个家族历史文化汇总的档案。家谱就是一个家族的生命史

家庭是社会机体的细胞，家族是民族大树的枝叶，家谱就是一个家族的生命史，档案史，文化史和百科全书。后人由此了解家族的历史沿革，世系繁衍，人口变化，居地变迁，对历史学，人口学，民信学，社会学和经济学等方面的研究有着不可替代的独特作用，家谱具有明辨世系，尊宗问祖，寻根谒祖，承前启后，敦亲睦祖，凝聚血亲，治家齐国，教化子孙，传承历史，弘扬文化等方面的功能。不但是家族历史文化的记录，也是天涯游子落叶归根的精神寄托，心灵皈依。因此续修家谱即是一个家族的头等大事，也关系到中华民族优秀传统文化的传承和发扬。

我的解法如下：

在族谱中人与人的关系是多对多的关系，所以设计数据结构的时候需要2张表，一张是家族成员表，一张是成员关系表。

ER图，如下：

这样，即可以通过长辈递归出所有的晚辈，也可以通过晚辈递归出所有的长辈。