學院新生求問 C 語言 recursive function

qiqimon5566

最近在拉曼學院學習advance function的recursive function
雖然我懂它的意思和做法
可是我實在不明白甚麼時候應該用recursive function
我問老師, 老師又說不知道怎樣解釋
她只會回答我 題目要我用的是時候就用 就寫==

我想請問這裡的高手們甚麼是recursive function
甚麼情況下 我們應該用它
聽說用過頭recursive function會造成program lag 那麼為甚麼還要用它呢?

希望得到各位前輩的解答^^
我目前就只會一個語言 C 語言
是networking的學生
請指教

我是Max

维奇

qiqimon5566

我是Max 发表于 23-12-2009 04:16 PM

請問甚麼來的==?

keat88

recursive function 是 在同一个function 里 call 回自己。。
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}


例如要算 factorial 的时候可以用

qiqimon5566

呵呵呵
樓上的抱歉
實在很抱歉我的觀察力太差了
我看多一次之後才發現原來是link
謝謝

我是Max

呵呵呵
樓上的抱歉
實在很抱歉我的觀察力太差了
我看多一次之後才發現原來是link
謝謝
qiqimon5566 发表于 23-12-2009 04:32 PM

用在Exponentiation。

int pow(int x,int y)
{    if(y==1) return x*x;           
      else return x*pow(x,y-1);
}
好像在negative有问题。。。

我是Max

自己多动手尝试，多试验。
好象经典的迷宫问题(maze)，也可以用recursive解决。
SotongJiang 发表于 23-12-2009 05:51 PM

recursive function 也可以用来尝试每种不同的可能性。

i-counsellor

recursive 最大好处是flexible size.
在一些特例子，可能你不能肯定你需要loop多少次，你call 同样的function和更改的var state,不断的looping直到var state符合terminate condition.

当然，recursive 其实是call function itself。每个function都是需要memory如果你用过头的话，你就会run out of memory.

晨天

最近在拉曼學院學習advance function的recursive function
雖然我懂它的意思和做法
可是我實在不明白甚麼 ...
qiqimon5566 发表于 23-12-2009 04:09 PM

Wiki 已经有解释

1. is a method where the solution to a problem depends on solutions to smaller instances of the same problem

复制代码

• 
  Factorial
• 
  Fibonacci
• 
  Greatest common divisor
• 
  Towers of Hanoi
• 
  Binary search

以上五个是较常用的 recursion example

我也不会如何解释给你听。。。

以前 geekman 大大 曾经 在这里解释过。。。
你不妨 用 cari search 看看

geekman

LZ，你的老师好强啊，不会还理直气壮。。。I服了She！

其实很多时候recurssive都可以用for loop或者while loop解决的。recursive的存在意义，就好像 i-counsellor 所说的，当你必须面对一个无法知道终止状况（但是知道终止条件）的情形下使用的。例如Fractal，因为种子和分歧条件的不同，你无法确定每个分叉运算会有多少个运算步骤，而是必须靠运算来判断终止状况的时候，就应该使用recursive。Recursive还有一个用loop无法轻易达到的特性，那就是每遇到分歧点，在完成了每个分支的运算后，它会倒退回到分歧点，这时你就可以进入另一个分歧去继续运算（你可以去看看Fractal Tree的原理，每个分歧点就是树枝的分叉）

qiqimon5566

回复 11# geekman

非常非常的感谢你的回答
mycari这里的确是高手如云
可惜只能自叹 自身悟性不足 欠缺慧根
我还是不能准确地明白 或许只明白了其中的30%
看来我还得加倍努力才行了

谢谢

onlylonly

回复 12# qiqimon5566


   不要灰心， 其实大学生， 很少看到在学习编程时， 会主动思考其中的原理， 何时运用等。 坚持着， 将来必定是个人才。

recursive 其好处是， 可以将非常复杂的问题， 以不断重复执行自己， 来达到简化问题的结果。 好比quick sort， 将整个 array 不断的 partition 自己， 来达到 sorting 的结果。 若是以 iterative 方式来编写， 就会显得非常的复杂。 而 recursive ， 就能让人一目了然， 让 code 更能明白。

其余的如 extended euclidean algorithm， GCD， binary search 等， 在 recursive 下的写法， 都会让 code 更容易 maintain， 更容易明白。让 code 更短， 更美

以后你接触多了， 就会发现 recursive 的奥妙， 及其的美丽。 你有时间， 也可以玩玩 tree 的写法， 一样会让你受益不浅。

k2powell

回复 12# qiqimon5566

一个简单的例子，比如说你有一个decision tree，而你又不知tree内有多少layer,但你又必须access每一个nodes。如果你用while-loop+for-loop，你的codes可能会很乱，很长。同样的问题如果用recursive，那就简单又干净。
用recursive最重要的是termination condition要正确，要不然可能会造成infinate loop。
现在你觉得用法模糊是OK的，重要的是要了解概念，当有一天你碰到没法用while-loop／for-loop解决，而recursive可以时你就懂得欣赏了

qiqimon5566

回复 14# k2powell


    有同感,可惜就是還沒找到解決不了的><"
真希望能找到那種題目
实战是最好的经验