Skip to main content

CS223 Exercises

Section 1.12 Homework 12 -- Recursion

Exercises Exercises

1.

True or False?
🔗
Like iteration, recursion is used to execute the same code repeatedly. However, unlike iteration, recursion does not use a loop to accomplish this.
🔗
  • True
  • False
🔗

2.

🔗

3.

When a new function call is made, which of the following is NOT saved as part of the activation record (a.k.a., stack frame) for that function when it is added to the top of the runtime stack?
🔗
  • the number of times the function has been called
  • variables defined locally in the function
  • function parameters and their values
  • location in the calling program to return to when the current function ends
🔗

4.

🔗

5.

Given the following recursive function definition:
🔗
void printNum(int num, int limit)
{
    cout << num;
    if (num < limit)
    {
        printNum(num + 1, limit);
    }
    cout << num;
}
What will be the output produced by the function call:
🔗
printNum(3, 6);
  • 34566543
  • 3456776543
  • 3456
  • 76543
🔗

6.

Write a recursive function, rec_is_pal, that takes a string and returns true if the string is a palindrome; otherwise, returns false. Each recursive call should be dealing with the question for a string with a smaller size.
🔗
For example:
🔗
Test Result 
if (rec_is_pal("racecar")) {
    cout << "PALINDROME";
else {
    cout << "not a palindrome";
}
🔗
 
PALINDROME
🔗
 
if (rec_is_pal("racebar")) {
    cout << "PALINDROME";
else {
    cout << "not a palindrome";
}
🔗
 
not a palindrome
🔗
 
if (rec_is_pal("abba")) {
    cout << "PALINDROME";
else {
    cout << "not a palindrome";
}
🔗
 
PALINDROME
🔗
 
if (rec_is_pal("ABCA")) {
    cout << "PALINDROME";
else {
    cout << "not a palindrome";
}
🔗
 
not a palindrome
🔗
🔗

7.

Write a recursive function, rec_choose, that takes two integers, `n` and `k`, and returns the value of n choose k.
🔗
The value [n choose k] represents the number of ways of picking k distinct objects out of a set of n distinct objects. For example, suppose we have four people; Alice (A), Balthazar (B), Charlize (C) and Douglass (D). How many ways could you pick a pair of them? Six: AB, AC, AD, BC, BD and CD. That is 4 choose 2 = 6.
🔗
The standard definition of n choose k involves factorials. However, there is also a recursive definition (Pascal’s Identity):
🔗
n choose k = (n-1 choose k-1) + (n-1 choose k), for 0 < k < n
The first base case is when k is out of range (k < 0 or k > n). It’s impossible to choose k items in this case, so the answer is 0.
🔗
The second base case is when k is 0. There is only one way to choose nothing, so the answer is 1.
🔗
The third base case is when k equals n. There is only one way to choose n things from n things, so the answer is 1.
🔗
For example:
🔗
Test Result 
cout << rec_choose(4, 2)
🔗
 
6
🔗
 
cout << rec_choose(3, 0)
🔗
 
1
🔗
 
cout << rec_choose(10, 4)
🔗
 
210
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext