递归调用很纠结(页 1) - 『数据结构与算法』

追忆似水年华 发表于 2010-9-4 16:21

递归调用很纠结

本人最近在学数据结构，总感觉自己的逻辑思维能力很差，一用到递归调用就不莫不着头脑，感觉算法里面好些技巧用了递归之后其实很简单
举个例子，求二叉树的高度的时候，只有用到递归，五六行的代码就搞定了。可自己还是琢磨不透；
int treehigh(Tree *t)
{
if(t == NULL)
{
      return 0;
}
else
{
      int rhigh=treehigh(t->right);
      int lhigh=treehigh(t->left);
      if(rlength > llength)
      {
         return (rhigh+1);
      }
      else
      {
         return (lhigh+1);
      }
}
}
自己很迷茫，不知道把递归理解透彻；
希望哪位大侠帮我讲解一下递归调用的过程；

makebest 发表于 2010-9-4 16:30

递归是大化小的原理, 求 T 的高
若 T 是空, 则高为 0
否则取左树和右树的高, 取其中较大的 +1 就是 T 的高
结了.

LegendofMine 发表于 2010-9-4 21:19

楼主不妨试试这样想，一个问题如果能找到递推公式，就可以用递归简化代码(许多时候用递归是很不可取的).
比如在这道题中，设以某一个结点p为跟的子树的高度为Hight(p)，那么有：
Hight(p)=max { Hight( child1(p) ) ,Hight( child2(p) ) ......Hight( childi(p) )....Hight ( childn(p) ) } +1  ,childi(p)表示p节点的各个子节点
在二叉树树中可以简单的表示为：
                        Hight( p->lchild ) +1 If Hight (p->lchild） >Hight( p->rchild )
   Hight(p)= 或，Hight( p->rchild ) +1 else

通过观察递推公式，就很容易清楚函数之间的调用关系了。

所以递推考验你的分析能力，还有比这更难理解的，不过比较熟知的题，比如二叉树这道题，慢慢地你就都会了。

wsliuyunming 发表于 2010-10-10 22:07

我也很迷茫对递归调用

promise90 发表于 2010-10-11 12:55

[b][i][color=#1ae61a]递归函数是一个自己条用自己的函数。[/color][/i][/b]

promise90 发表于 2010-10-11 12:57

调用。。。一段给定的代码对自身的进行调用，知道某些边界条件得到满足。

页: [1]