(6.2)--6.2Recursivealgorithm.pdf

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 realize 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 sequence(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 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=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 Chinese)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 call 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,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 algorithm6.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: