CH10-遞歸(Recursion)

1、1、求階乘、求階乘Informal definition: The factorial function of a positive integer is n! = 1 (n=0) n * (n - 1) ! ( n0)Every recursive process consists of two parts(每個遞歸過程分成兩部分每個遞歸過程分成兩部分) A smallest, base case that is processed without recursion; (最最基本的部分基本的部分(基例基例)不需要遞歸不需要遞歸) A general method that reduces

2、a particular case to one or more of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case.(一般的過程需要拆開為可以小規(guī)模一般的過程需要拆開為可以小規(guī)模)main 第第1 1次調(diào)用次調(diào)用 第第2 2次調(diào)用次調(diào)用 第第3 3次調(diào)用次調(diào)用 第第4 4次調(diào)用次調(diào)用 f1(4) n=4 n=3 n=2 n=1 return 4*f1(3) return 3*f1(2) return 2*f1(1) r

3、eturn 1 return 2*1 return 3*2 return 4*6 24long f1 ( int n ) long r; if (n=1) r = 1; else r=n*f1(n-1); return (r); 遞歸遞歸返回返回過程過程遞歸遞歸調(diào)用調(diào)用過程過程long factolong facto ( int n ) ( int n ) long r; long r; if ( n if ( n = 1 ) 1 ) r = 1; r = 1; else else r = n r = n * * factofacto(n-1); (n-1); return (r); return (r); 當(dāng)當(dāng) n = 1 n = 1 時時n! = 1n! = 1當(dāng)當(dāng) n 1 n 1 時時n! = n n! = n * * (n-1)! (n-1)!返回返回N=4N=3N=2N=1move(count - 1, start, temp, finish); move(count - 1, temp, finish, start); return fib (n - 1) + fib (n - 2);遞歸樹（遞歸樹（ Recursion TreesRecursion Trees）fib (5)fib (4)fib (3)+fib (3)fib (2)+fib(2)fib(1)+