Analysis and Design of Algorithms Analysis and Design of Algorithms Transform CodingChapter 3: Recursive AlgorithmSchool of Software Engineering ©Yanling XuRecursive Algorithm Recursive AlgorithmRecursion :a procedure or subroutine, whose implementation references itselfE l 1R i l ti f !Example 1: Recursive evaluation of n ! ⎧n initial condition 00)!1(1!>=⎩⎨−=n n n n recurrence relationC(n)=C(n 1)+1Times of Basic operation for n ! C()C(n-1)+1 =[C(n-2)+1]+1 = C(n-2)+2=[C(n-3)+1]+2 = C(n-3)+3Iterative DefinitionC(n)=n ……=[C(n-n)+1]+n-1 = n2nn n ×××××=）－（1...321!Recursive AlgorithmRecursive AlgorithmExample 4: The Tower of Hanoi Puzzlevoid hanoi(int n, int a, int b, int c){if (n > 0)if(0){hanoi(n-1, a, c, b);move(a,b);(b)hanoi(n-1, c, b, a);}}C(n) ∈Θ (2n)C(n) = 2C(n –1) + 1 =2n-1 for every n > 05Recursive AlgorithmRecursive AlgorithmExample 5: permutation problem 排列问题设计一个递归算法生成n个元素{r,r2,…,r n}的全排列。
•设R={r1,r2,…,r n}是要进行排列的n个元素，R i=R-{r i}。
•集合X中元素的全排列记为perm(X)。
•(r i)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。
•R的全排列可归纳定义如下：的排列可归纳定义如下当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；)perm(R1)，(r2)perm(R2)，…，(r n)perm(R n)构成。
当n>1时，perm(R)由(r16Recursive Algorithm Recursive AlgorithmExample 5: permutation problem (‘cont)template <class Type>void Perm(Type list[],int k,int m){// create all permutation of list [k: m ]with prefix list[0,k-1]onl one element to be done if (k ==m){//only one element to be done for (int i =0;i <=m;i++) putchar(list[i]); putchar(‘\n’); p ();}else //several permutations for list[k: m ] are created by recursive for (i=k;i <=m;i++){ S (li t[k]li t[i])Swap (list[k],list[i]); Perm (list,k+1,m);// Swap (list [k],list [i]);} }inline void Swap(Type &a,Type &b) {T t b t }7Type temp =a; a =b; b =temp; }Recursive AlgorithmRecursive AlgorithmExample 6: partition problem 整数划分将正整数n表示成一系列正整数之和：n=n1+n2+…+n k.▪其中n1≥n2≥…≥n k≥1，k≥1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数q(n)。
▪ e.g. 正整数6有如下11种不同的划分, q(6)=116；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+18Recursive AlgorithmRecursive AlgorithmExample 6: partition problem (‘cont)将最大加数n1不大于m的划分个数记作q(n,m)()可以建立q(n,m)的如下递归关系:•q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。
•q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;q()q()q()正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1 的划分组成。
9Recursive Algorithm Recursive AlgorithmExample 6: partition problem (‘cont)Recursive definition⎧⎪⎪⎨=<==−+=1,1)1,(1),(1),(m n m n m n n n q n n q m n q ⎪⎪⎩>>−+−1),()1,(m n m m n q m n q int q(int n,int m){if (n <1||m <1)return 0;if (n ==1||m ==1)return 1;if (n q(n if (n <m)return q(n,n);if (n ==m)return q(n,m -1)+1;return q(n,m -1)+q(n -m,m));}10Recursive Algorithm Recursive AlgorithmImportant Recurrence TypeDecrease-by-one recurrencesA decrease-by-one algorithm solves a problem by exploiting a relationship between a given instance of size n and a smaller size n –1.Example: n! The recurrence equation for investigating the time efficiency of The recurrence equation for investigating the time efficiency of such algorithms typically has the formT(n) = T(n-1) + f(n)Decrease-by-a-constant-factor recurrences Decrease by a constant factor recurrences A decrease-by-a-constant algorithm solves a problem by dividing its given instance of size n into several smaller instances of size n/b,solving each of them recursively,and f ,g f y,then,if necessary,combining the solutions to the smaller instances into a solution to the given instance. Example: binary search.11The recurrence equation for investigating the time efficiency ofsuch algorithms typically has the formT(n) = aT(n/b) + f (n)Recursive AlgorithmRecursive Algorithm Decrease-by-a-constant-factor recurrences –The Master TheoremT (n ) = aT (n/b ) + f (n ),where f (n )∈Θ(n k ), k>=01. a < b k T (n ) ∈Θ(n k )2. a = b k T (n ) ∈Θ(n k log n )3. a > b k T (n ) ∈Θ(n log b a ) Example:T()T(/2)+1(l ) T(n) = T(n/2) + 1 Θ(logn) T(n) = 2T(n/2) + n Θ(nlogn) T(n)=3T(n/2)+n log 312T(n) 3 T(n/2) + n Θ(n 2)。
