C语言编程学习课件 (38).pdf
Programming In CProgramming In C deeper and deeper deeper and deeper into the dreaminto the dream “Recursion is nesting,all kinds of nesting.(Story in story,movie in movie,picture in picture,etc.)”Step 1:move the smallest plate 3 from tower A to tower C Step 2:move the second smallest plate 2 from tower A to tower B Step 3:move plate 3 from tower C to tower B Programming In CProgramming In C void hanoi(int n,char A,char B,char C)if(n=1)move(A,C);/recursive exits/recursive exits else /three Steps/three Steps hanoi(n-1,A,C,B);/Recursive reduction/Recursive reduction move(A,C);hanoi(n-1,B,A,C);/Recursive reduction/Recursive reduction Programming In CProgramming In C void move(char get,char put)printf(%c-%cn,get,put);void main()int n;printf(input the number of diskes:n);scanf(%d,&n);printf(The step to moving%d diskes:n,n);hanoi(n,A,B,C);Programming In CProgramming In C Programming In CProgramming In C If the number of plates is 10,it needs to be moved 1023 times.When the number of plates is 64,it needs to be moved about 184.4 billion times.If each move takes 1 microsecond,it will take 600,000 years to complete the operation.However,the Hanoi()function can achieve such complicated operations in less than 10 lines of code.How simple and efficient it is!Programming In CProgramming In C In mathematics and computer science,recursion refers to a method of using the function itself in the definition of the function.A prerequisite that a problem can be a recursive problem is:The latter part is similar to the original question,and the latter part is a simplification of the original question.A recursive function must contain two basic elements:First,there must be iterative processes(to call itself)，Second,there must be conditions to jump out of the iterative process(to set up recursive exits).9 emmemm，I am 6I am 6 6 6岁岁 1010 I am 14I am 14 int age(int n)if(n=1)return(6);else return(age(n-1)+2);age(1)int age(int n)if(n=1)return(6);else return(age(n-1)+2);age(2)int age(int n)if(n=1)return(6);else return(age(n-1)+2);age(3)int age(int n)if(n=1)return(6);else return(age(n-1)+2);age(4)main().age(5)4 n n 3 n n 2 n n 12 8 10 6 1 n n int age(int n)if(n=1)return(6);else return(age(n-1)+2);age(5)18 5 n n Programming In CProgramming In C In this example,we make the same recursion from the age of the fifth child to the age of the first child step by step.Knowing the age of the first child,we can deduce the age of others.The process of solving this problem meets the requirements of recursive functions,so we can use recursive functions to solve this problem.First,build the age recursive model age(n):When n is 1,the result is 6,which is the recursive exit,When n is greater than one,add two to the age of the(n-1)person.Programming In CProgramming In C Then,write the corresponding recursive function age(),The formal parameter n represents the nth person:if n=1,it returns 6，else return age(n-1)+2.Finally,the age()function is called in main(),and this problem can be solved.Programming In CProgramming In C Essentially,recursion is nesting.Advantages of recursion：Firstly,the structure is clear;secondly,it is readable;thirdly,it is easy to prove the correctness of the algorithm by mathematical induction.Therefore,it brings great convenience to designing algorithms and debugging.Disadvantages of recursion：The recursive algorithm is relatively inefficient.It takes more computing time and memory space than non-recursive algorithm.Programming In CProgramming In C 1（n=0,1）n*(n-1)!（n1）n!=Calculate n factorial with recursionCalculate n factorial with recursion Programming In CProgramming In C
