CS代考 CS2310 Computer Programming

Computer Science, City University of
Semester B 2021-22
CS2310 Computer Programming

Copyright By PowCoder代写 加微信 powcoder

LT12: Recursion

A recursive function is a function that calls itself

Recursive functions can be useful in solving problems that can be broken down into smaller or simpler sub-problems of the same type

A base case should eventually be reached, at which time the breaking down (recursion) will stop

Problem of Recursive Nature
The factorial function
6! = 6 * 5 * 4 * 3 * 2 * 1

We could write:
6! = 6 * 5!

Problem of Recursive Nature
In general, we can express the factorial function on the last slide as follows:
n! = n * (n-1)!

Is this enough?
The factorial function is only defined for positive integers. So we should be a bit more precise:
n! = 1 (if n is equal to 1)
n! = n * (n-1)! (if n is larger than 1)

Problem of Recursive Nature
The C++ equivalent of this definition:

int fac(int numb){
if(numb<=1) return numb * fac(numb-1); Assume the number typed is 3, that is, n=3. int fac(int numb){ if(numb<=1) return numb * fac(numb-1); 3 <= 1 ? No. fac(3) = 3 * fac(2) 2 <= 1 ? No. fac(2) = 2 * fac(1) 1 <= 1 ? Yes. fac(2) = 2 * 1 = 2 return fac(2) fac(3) = 3 * 2 = 6 return fac(3) fac(3) has the value 6 Problem of Recursive Nature Problem of Recursive Nature For certain problems (such as the factorial function), a recursive solution often leads to short and elegant code. Compare the recursive solution with the iterative solution: Recursive solution int fac(int numb){ if(numb<=1) return numb*fac(numb-1); Iterative solution int fac(int numb){ int product=1; while(numb>1){
product *= numb;
return product;

If we use iteration, we must be careful, not to create an infinite loop by accident:

for(int incr=1; incr!=10;incr+=2)

int result = 1;
while(result >0){

Similarly, if we use recursion, we must be careful not to create an infinite chain of function calls:
int fac(int numb){
return numb * fac(numb-1);
int fac(int numb){
if (numb<=1) return numb * fac(numb+1); No termination condition We must always make sure that the recursion bottoms out A recursive function must contain at least one non-recursive branch The recursive calls must eventually lead to a non-recursive branch Recursion is one way to decompose a task into smaller subtasks. At least one of the subtasks is a smaller example of the same task The smallest example of the same task has a non-recursive solution Example: The factorial function n! = n * (n-1)! and 1! = 1 How to write exp(int n, int p) recursively? E.g., exp(n, p) = np int exp(int n, int p){ if(p == 0) return n * exp(n, p-1); Example: Exponential func. Write a recursive function that counts the number of zero digits in an integer, n E.g., if n is 10200, zeros(10200) returns 3 How to decompose? Base cases? If digit is ?, return ? If digit is ?, return ? Example: number of zero zeros(10200) zeros(1020) + zeros(0) zeros(102) + zeros(0) + zeros(0) zeros(10) + zeros(2) + zeros(0) + zeros(0) zeros(1) + zeros(0) + zeros(2) + zeros(0) + zeros(0) Write a recursive function that counts the number of zero digits in an integer zeros(10200) returns 3 int zeros(int numb){ if(numb==0) // 1 digit (zero/non-zero): return 1; // bottom out. else if(numb < 10 && numb > -10)
else // > 1 digits: recursion
return zeros(numb/10) + zeros(numb%10);
Example: number of zero

Example: printing
Printing a message for n times
E.g., void nPrintln(char* message, int n)

We can break the problem into two sub-problems:
One is to print the message one time and
The other is to print the message for n-1 times.
The second problem is the same as the original problem with a smaller size. The base case for the problem is n==0
void nPrintln(char * message, int times)
if (times >= 1) {
cout << message << endl; nPrintln(message, times - 1); } // The base case is n == 0 Example: greatest common divisor greatest common divisor (gcd) of two positive integers is the largest integer that divides evenly into both of them E.g., gcd(102, 68) = 34 Expression: If p > q, the gcd of p and q is the same as the gcd of q and p % q.

/docProps/thumbnail.jpeg

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com