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