《(6.2)--6.2Recursivealgorithm.pdf》由会员分享，可在线阅读，更多相关《(6.2)--6.2Recursivealgorithm.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Recursive algorithmRecursive algorithm6.2For some problems,the sub-problems to be solved after the modulardecomposition have the same characteristics and solutions as the originalproblem,but with reduced scales.Recursive algorithm can be used to solvesuch problems.Recursive function is used to reali
2、ze recursive algorithm.A functiondirectly or indirectly calls itself to complete a calculating process.The waythat a function calls itself directly or indirectly is called a recursive call.Recursive algorithmRecursive algorithm6.2Eg1Design a recursive algorithm to find the value of Fibonacci sequenc
3、e(1,1,2,3,5,8,13,).Decompose the original problem into:The n-th term equals thesum of the(n-1)-th term and(n-2)-th term.After decomposition,the calculating method of the(n-1)-thand(n-2)-th term in the sub-problems are exactly the same asthat of the original problem,but with reduced scales.Theproblem
4、 can be decomposed recursively,until the sub-problemis to calculating the value of the 1st or 2nd term,which shoulddirectly return 1.Problem solving using computational thinking:Recursive algorithm6.2Therefore,the recursive algorithm for solving this problem can be designed as following:If n=1 or n=
5、2The value is 1otherwiseThe value equals the sum of the values of(n-1)-the and(n-2)-th term Recursive algorithm6.2Eg2Write a recursive function to find the value of the n-th term in Fibonacci sequence.int F(int n)if(n=1|n=2)return 1;elsereturn F(n-1)+F(n-2);Recursive algorithm6.2(1)Recursive(Di in C
6、hinese)processing:when writing a recursive function,first assume that the function has already been implemented and can be called directly.For example,when writing the F function,we can calculate F(n)using the statement F(n-1)+F(n-2);.(2)Return(Gui in Chinese)processing:the function of recursive cal
7、l must have a conditional statement that can end the recursive call,otherwise it will continue to be called recursively,leaving the program unresponsive.For example,when calculating the n-th term of Fibonacci sequence recursively,if the value of n is 1 or 2,there is no need to perform recursion call
8、,and the function should directly return 1.Tips:Recursive algorithm6.2Eg3Write a program to find the value of n-th term in Fibonacci sequence.#include using namespace std;int F(int n);/function declarationint main()int n=5;cout The”n -th term in Fibonacci sequence is F(n)endl;return 0;Recursive algo
9、rithm6.2int F(int n)if(n=1|n=2)return 1;elsereturn F(n-1)+F(n-2);Recursive algorithm6.2(a)The process of top-down decomposition(b)The process of bottom-up decompositionF(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)=53+21+12+11+1Recursive algorithm6.2What about the recursive algorithm for calculating n!Question: