linux&c++ R&D

programing is a pleasure!

Thinking recursively

First,Let's know the principle:
Recursive leap of faith-
When you try to understand a recursive program,you must be able to put the underlying details aside and focus instead on a single level of the operation. At that level,you are allowed to assume that any recursive call automatically gets the right answer as long as the arguments to that call are simpler than the original arguments in some respect.The psychological strategy-assuming that any simpler recursive call will work correctly-is called the recursive leap of faith!
The idea may be difficult to newers! Take an example for it:
We all know the Fibonacci function:
F(n)=F(n-1)+F(n-2)
Recursive implementation of the Fibonacci funtion:

int Fib(int n){
if (n<=1)
   
return n;
 
else
   
return Fib(n-1)+Fib(n-2);
}

 if n is 5,Fib(5) is computed by the sum of Fib(4) and Fib(3).
Applying the faith,you can assume that  the program correctly computes each of these values,without going through all the steps that Fib(4) and Fib(3) is computed!

posted on 2008-03-16 18:54 丑石 阅读(276) 评论(0)  编辑 收藏 引用 所属分类: Algorithm and Data Structure


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

News

常用链接

留言簿(1)

随笔分类(13)

随笔档案(17)

文章档案(1)

相册

收藏夹(1)

Friends' blog

useful sites

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜