Factorials: A Recursive Definition Informal definition: The factorial function of a positive integer IS n!=nx(n-1)x.XI 定义是递归的 Formal definition 雪n=0时 n*(n-1)!,当n≥1时
Factorials: A Recursive Definition Informal definition: The factorial function of a positive integer is n! = n(n-1)…1 Formal definition: − = = 当 时 当 时 n (n 1)!, n 1 1, n 0 n! 定义是递归的
boundary Every recursive processconsists of two parts: A smallest, base case that is processed without recursion and recursion a general method that reduces a particular case to one or more ot the smaller cases thereby making progress toward eventually reducing the problem all the way to the base case
Every recursive process consists of two parts: A smallest, base case that is processed without recursion; and A general method that reduces 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. boundary recursion
Towers of hanoi 问题的解法是递归的 Rules: Move only one disk at a time. No larger disk can be on top of a smaller disk
Towers of Hanoi Rules: Move only one disk at a time. No larger disk can be on top of a smaller disk. 问题的解法是递归的
void move int count, int start, int finish, int temp); / Pre: There are at least count disks on the tower start.The top disk(if any) on each of towers temp and finish is larger than any of the top count disks on tower start. Post: The top count disks on start have been moved to finish tempused for temporary storage has been returned to its starting position. / const int disks 64. // Make this constant much smaller to run program. void move(int count, int start, int finish, int temp); Pre: None. Post: The simulation of the Towers of Hanoi has terminated. /
void move(int count, int start, int finish, int temp); /* Pre: There are at least count disks on the tower start. The top disk (if any) on each of towers temp and finish is larger than any of the top count disks on tower start. Post: The top count disks on start have been moved to finish; temp (used for temporary storage) has been returned to its starting position.*/ const int disks = 64; // Make this constant much smaller to run program. void move(int count, int start, int finish, int temp); /* Pre: None. Post: The simulation of the Towers of Hanoi has terminated. */
main( i move(disks, 1, 3, 2);3 void move(int count, int start int nish, int temp) i if (count>O i move count-1, start, temp, nish); cout < Move disk < count < from < start < to<< finish <<< endl move count-1, temp, nish, start; Please see pg. 166-167 figure 5. 4-5.5
main( ) { move(disks, 1, 3, 2); } void move(int count, int start, int nish, int temp) { if (count > 0) { move(count - 1, start, temp, nish); cout << "Move disk " << count << " from " << start << " to " << finish << "." << endl; move(count - 1, temp, nish, start); } } Please see pg. 166-167 figure 5.4 - 5.5