Question

LANGUAGE IS C++

Lab Ch14 Recursion

In this lab, you are provided with startup code which has six working functions that use looping (for, while, or do loops) to repeat the same set of statements multiple times. You will create six equivalent functions that use recursion instead of looping. Although looping and recursion can be interchanged, for many problems, recursion is easier and more elegant.

Like loops, recursion must ALWAYS contain a condition; otherwise, you have an infinite recursion (or loop). The condition decides whether to: 1) call the function again; or 2) return from the function.

If you call the function again, the recursion is going deeper (diving into the rabbit hole); if you return from the function, the iteration is unwinding or unravelling itself (climbing out of the rabbit hole).

The main work performed in a recursive call can occur near the top (head) or bottom (tail) of the function. Specifically, the “work” can occur BEFORE or AFTER the recursive call. If the work occurs BEFORE the recursive call, this is sometimes called "head" recursion. If the work occurs AFTER the return from the recursive call, this is “tail" recursion. Of course, “work” can be performed both before and after the recursive call. But usually, recursive functions do most of their “work” BEFORE (on the way in), or AFTER (on the way out) of the recursive function.

void head(T n) {                  void tail(T n) {
    statements; // on the way in
    if (condition involving n)      if (condition involving n) {
    head(modified n);               tail(modified n);
                                      statements; // on the way out
                                    }
}                                 }

A void return is not required. See the textbook, Chapter 14, for many examples. Some languages, like lisp, are designed to use recursion extensively.

When executing a sequence of recursive calls, you control the "order of operation" by inserting processing steps anywhere into the templates above and choosing where you want the work to be done. If things are not getting done in the right order, try moving the processing steps above or below the: 1) decision; 2) recursive call; and/or swap whether doing head or tail recursion.

If you create an infinite recursion, the program will not hang (like an infinite loop); instead, the program will crash due to memory exhaustion. Unlike a loop, each recursive call uses up more memory (on the stack). The stack will quickly be used up during "infinite" recursion, and the program will crash - out of memory.

void infinite(T n) {
// no change to n before recursive call
infinite(n);
}

To avoid an infinite recursion, some progress must be made during each recursive call. The problem being passed to the recursive call MUST be simpler than the initial problem presented to the function. The problem must be simplified until it reaches a “base case” which avoids further recursive calls.

Problems to be solved in pairs, iteratively (provided) and recursively (you provide):
1) display a list of numbers increasing from 1 to n
2) display a list of numbers decreasing from n to 1
3) reverse a string (show a palindrome)
4) add two numbers together (cannot use + or - operator)
5) multiply two numbers together (cannot use * or / operator)
6) search for a number in an array

Scoring: 5 points per problem solved, total of 30 points. Extra credit: choose a looping algorithm NOT found in chapter 14, and implement BOTH a looping solution AND a recursive solution. For example, can you draw a diamond using both iteration and recursion? Can you sort an array both iteratively and recursively? Once you get the hang of it, you can do ANY looping (also called: “iterative”: 1, 2, 3, …) operation with recursion.

In your code, provide the body of the code for the (6) recursive functions. You do NOT have to change anything in main(). All the looping functions are provided. All the recursive prototypes are provided. All the calls in main are provided. Your job is to fill in the body of the code for the recursive functions. The functions to be written are very small, only about 3 to 5 lines of code. In ALL cases, the recursive solution MUST NOT use any loops!! Function show_test() is used to organize and simplify testing output.

IMPORTANT: Your recursive functions should NOT use any static local variables or global variables! The “state” of the function must be completely self-contained. Consider that recursive functions may be called simultaneously by several programs at the same time. This occurs when a recursive function is in a library, such as qsort(). If calls are not independent, the recursive function is limited to a single process.

START UP CODE:

/*
  For each looping function, provide the code for the equivalent recursive function.
  See Blackboard, Lab 14 for complete instructions.
  
  IMPORTANT: Your recursive functions should NOT use any static local variables
  or global variables! The "state" of the function must be completely self-contained.
  Consider that recursive functions may be called simultaneously by several programs
  at the same time. This occurs when a recursive function is in a library, such
  as qsort(). If calls are not independent, the recursive function is limited
  to a single process.
*/
  
#include <iostream>
#include <iomanip>
using namespace std;

void show_1_to_n_loop(int n) { // looping
  for (int i=1; i<=n; ++i) cout<<i<<" ";
}

void show_1_to_n_recurse(int n) { // recursive
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
}

void show_n_to_1_loop(int n) { // looping
  for (int i=n; i>=1; --i) cout<<i<<" ";
}

void show_n_to_1_recurse(int n) { // recursive
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
}

string reverse_loop(string forward) { // looping
  string backwards;
  int size=forward.size();
  for (int i=0; i<size; ++i) {
    backwards+=forward[size-1-i];
  }
  return backwards;
}

string reverse_recurse(string forward) { // recursive
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
  return ""; // replace this with your return value;  is "" until new code added.
}

int add2_fx(int a, int b) { // functional (for illustration only)
  return a+b;
}

int add2_loop(int a, int b) { // looping
  int sum=a;
  if (b>0)
    for (int i=0; i<b; ++i) ++sum;
  else // b<=0
    for (int i=b; i<0; ++i) --sum;
  return sum;
}

int add2_recurse(int a, int b) { // recursive
  // Rule: you may NOT use the *, /, +, =, *=, /=, +=, -= operators.
  // You MAY use: ++ and/or -- (as done in add2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
  return 0; // replace this with your return value;  is 0 until new code added.
}

int mult2_fx(int a, int b) { // functional (for illustration only)
  return a*b;
}

int mult2_loop(int a, int b) { // looping
  int product=0;
  if (b>0)
    for (int i=0; i<b; ++i) product+=a;
  else // b<=0
    for (int i=b; i<0; ++i) product-=a;
  return product;
}

int mult2_recurse(int a, int b) { // recursive
  // Rule: you may NOT use the *, *=, / or /= operators.
  // You MAY use: +, -, +=, -= operators (as done in mult2_loop)
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
  return 0; // replace this with your return value;  is 0 until new code added.
}

int search_loop(int array[], int size, int target) { // looping
  for (int i=0; i<size; ++i)
    if (array[i]==target) {return i;}
  return -1;
}

int search_recurse(int array[], int size, int target) { // recursive
  // Constraints: No loops allowed; no static local or global variables.
  // Your new code goes here...
  return 0; // replace this with your return value;  is 0 until new code added.
}

enum control_t {functional, looping, recursive};
void show_test(int n, string s, control_t control) {
  // utility function to format test output
  // n: test number; s: "description"; control: looping or recursive
  static const string fx="functional", sl="looping", sr="recursive";
  int max_len=max(fx.size(), max(sl.size(), sr.size()));
  string msg;
  switch (control) {
    case functional: msg=fx;     break;
    case looping:    msg=sl;     break;
    case recursive:  msg=sr;     break;
    default:         msg="??";   break;
  }
  char iorr=msg[0];
  msg=" ("+msg+"): ";
  cout<<"\n"<<n<<iorr<<") "<<s<<setw(max_len+5)<<left<<msg;
}

void infinite_recursion() {
  // try at your own risk! Error message can be interesting.
  infinite_recursion();
}

int main () {
  cout<<"start...\n";
  
  show_test(1, "show_1_to_n", looping);    show_1_to_n_loop(7);
  show_test(1, "show_1_to_n", recursive);  show_1_to_n_recurse(7);
  cout<<endl;
  
  show_test(2, "show_n_to_1", looping);    show_n_to_1_loop(10);
  show_test(2, "show_n_to_1", recursive);  show_n_to_1_recurse(10);
  cout<<endl;
  
  show_test(3, "reverse", looping);    cout<<reverse_loop("stressed");
  show_test(3, "reverse", recursive);  cout<<reverse_recurse("stressed");
  cout<<endl;

  show_test(4, "add2", functional);
  cout<<add2_fx( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_fx(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_fx(20, -9); cout<<" ";  // correct:  11
  cout<<add2_fx(-7, -5); cout<<" ";  // correct: -12
  show_test(4, "add2", looping);
  cout<<add2_loop( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_loop(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_loop(20, -9); cout<<" ";  // correct:  11
  cout<<add2_loop(-7, -5); cout<<" ";  // correct: -12
  show_test(4, "add2", recursive);
  cout<<add2_recurse( 4,  5); cout<<" ";  // correct:   9
  cout<<add2_recurse(-5, 15); cout<<" ";  // correct:  10
  cout<<add2_recurse(20, -9); cout<<" ";  // correct:  11
  cout<<add2_recurse(-7, -5); cout<<" ";  // correct: -12
  cout<<endl;

  show_test(5, "mult2", functional);
  cout<<mult2_fx( 2,   5); cout<<" ";  // correct:  10
  cout<<mult2_fx(-4,   5); cout<<" ";  // correct: -20
  cout<<mult2_fx( 3, -10); cout<<" ";  // correct: -30
  cout<<mult2_fx(10,   4); cout<<" ";  // correct:  40
  show_test(5, "mult2", looping);
  cout<<mult2_loop( 2,   5); cout<<" ";  // correct:  10
  cout<<mult2_loop(-4,   5); cout<<" ";  // correct: -20
  cout<<mult2_loop( 3, -10); cout<<" ";  // correct: -30
  cout<<mult2_loop(10,   4); cout<<" ";  // correct:  40
  show_test(5, "mult2", recursive);
  cout<<mult2_recurse( 2,   5); cout<<" ";  // correct:  10
  cout<<mult2_recurse(-4,   5); cout<<" ";  // correct: -20
  cout<<mult2_recurse( 3, -10); cout<<" ";  // correct: -30
  cout<<mult2_recurse(10,   4); cout<<" ";  // correct:  40
  cout<<endl;
  
  int primes[] {2, 3, 5, 7, 11, 13, 17}; // some prime numbers to search for
  int size_primes=sizeof(primes)/sizeof(int);
  
  show_test(6, "search", looping);
  cout<<search_loop(primes, size_primes, 2)<<", ";
  cout<<search_loop(primes, size_primes, 13)<<", ";
  cout<<search_loop(primes, size_primes, 10);
  show_test(6, "search", recursive);
  cout<<search_recurse(primes, size_primes, 2)<<", ";
  cout<<search_recurse(primes, size_primes, 13)<<", ";
  cout<<search_recurse(primes, size_primes, 10)<<endl;
  
  // uncomment the next line for crash and error message...
  // infinite_recursion();
  
  cout<<"\n...end\n";

  return 0;
} // end of main

// When complete, there will be test output for each of the 6 steps in pairs:
// looping and recursive, as shown below. Your recursive output should match.
/*
start...

1l) show_1_to_n (looping):    1 2 3 4 5 6 7
1r) show_1_to_n (recursive):

2l) show_n_to_1 (looping):    10 9 8 7 6 5 4 3 2 1
2r) show_n_to_1 (recursive):

3l) reverse (looping):    desserts
3r) reverse (recursive):

4f) add2 (functional): 9 10 11 -12
4l) add2 (looping):    9 10 11 -12
4r) add2 (recursive):  0 0 0 0

5f) mult2 (functional): 10 -20 -30 40
5l) mult2 (looping):    10 -20 -30 40
5r) mult2 (recursive):  0 0 0 0

6l) search (looping):    0, 5, -1
6r) search (recursive):  0, 0, 0

...end
*/

Answer 1

Working code implemented in C++ and appropriate comments provided for better understanding:

Source code for main.cpp:

/*
For each looping function, provide the code for the equivalent recursive function.
See Blackboard, Lab 14 for complete instructions.

IMPORTANT: Your recursive functions should NOT use any static local variables
or global variables! The "state" of the function must be completely self-contained.
Consider that recursive functions may be called simultaneously by several programs
at the same time. This occurs when a recursive function is in a library, such
as qsort(). If calls are not independent, the recursive function is limited
to a single process.
*/

#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

void show_1_to_n_loop(int n)
{ // looping
for (int i = 1; i <= n; ++i)
cout << i << " ";
}

void show_1_to_n_recurse(int n)
{
if (n > 0)
{
show_1_to_n_recurse(n - 1);
// tail end to be in correct order
cout << n << " ";
}
}

void show_n_to_1_loop(int n)
{ // looping
for (int i = n; i >= 1; --i)
cout << i << " ";
}

void show_n_to_1_recurse(int n)
{
if (n > 0)
{
cout << n << " ";
show_n_to_1_recurse(n - 1);
}
}

string reverse_loop(string forward)
{ // looping
string backwards;
int size = forward.size();
for (int i = 0; i < size; ++i)
{
backwards += forward[size - 1 - i];
}
return backwards;
}

string reverse_recurse(string forward)
{
if (forward.size() == 1)
{
return forward;
}
else
{
// tail call work; so after one call "tressed" will be passed as new param and s will be the last letter
return reverse_recurse(forward.substr(1, forward.size())) + forward.at(0);
}
}

int add2_fx(int a, int b)
{ // functional (for illustration only)
return a + b;
}

int add2_loop(int a, int b)
{ // looping
int sum = a;
if (b > 0)
for (int i = 0; i < b; ++i)
++sum;
else // b<=0
for (int i = b; i < 0; ++i)
--sum;
return sum;
}

int add2_recurse(int a, int b)
{ // recursive
// Rule: you may NOT use the *, /, +, =, *=, /=, +=, -= operators.
// You MAY use: ++ and/or -- (as done in add2_loop)
if (b > 0)
{
return add2_recurse(++a, --b);
}
else if (b < 0)
{
return add2_recurse(--a, ++b);
}
else
{
return a;
}
}

int mult2_fx(int a, int b)
{ // functional (for illustration only)
return a * b;
}

int mult2_loop(int a, int b)
{ // looping
int product = 0;
if (b > 0)
for (int i = 0; i < b; ++i)
product += a;
else // b<=0
for (int i = b; i < 0; ++i)
product -= a;
return product;
}

int mult2_recurse(int a, int b)
{ // recursive
if (a == 0 || b == 0)
{
return 0;
}

// used to store the sign of the first call
int temp_a = a;
int temp_b = b;

a = abs(a);
b = abs(b);
int sum = a += mult2_recurse(a, --b);

if (!(temp_a < 0) != !(temp_b < 0))
{
return -sum;
}
else
{
return sum;
}
}

int search_loop(int array[], int size, int target)
{ // looping
for (int i = 0; i < size; ++i)
if (array[i] == target)
{
return i;
}
return -1;
}

int search_recurse(int array[], int size, int target)
{ // recursive
if (size < 0)
{
// result not found
return -1;
}

if (array[size] == target)
{
// target found
return size;
}

return search_recurse(array, size - 1, target);
}

enum control_t
{
functional,
looping,
recursive
};
void show_test(int n, string s, control_t control)
{
// utility function to format test output
// n: test number; s: "description"; control: looping or recursive
static const string fx = "functional", sl = "looping", sr = "recursive";
int max_len = max(fx.size(), max(sl.size(), sr.size()));
string msg;
switch (control)
{
case functional:
msg = fx;
break;
case looping:
msg = sl;
break;
case recursive:
msg = sr;
break;
default:
msg = "??";
break;
}
char iorr = msg[0];
msg = " (" + msg + "): ";
cout << "\n"
<< n << iorr << ") " << s << setw(max_len + 5) << left << msg;
}

void infinite_recursion()
{
// try at your own risk! Error message can be interesting.
infinite_recursion();
}

int main()
{
cout << "start...\n";

show_test(1, "show_1_to_n", looping);
show_1_to_n_loop(7);
show_test(1, "show_1_to_n", recursive);
show_1_to_n_recurse(7);
cout << endl;

show_test(2, "show_n_to_1", looping);
show_n_to_1_loop(10);
show_test(2, "show_n_to_1", recursive);
show_n_to_1_recurse(10);
cout << endl;

show_test(3, "reverse", looping);
cout << reverse_loop("stressed");
show_test(3, "reverse", recursive);
cout << reverse_recurse("stressed");
cout << endl;

show_test(4, "add2", functional);
cout << add2_fx(4, 5);
cout << " "; // correct: 9
cout << add2_fx(-5, 15);
cout << " "; // correct: 10
cout << add2_fx(20, -9);
cout << " "; // correct: 11
cout << add2_fx(-7, -5);
cout << " "; // correct: -12
show_test(4, "add2", looping);
cout << add2_loop(4, 5);
cout << " "; // correct: 9
cout << add2_loop(-5, 15);
cout << " "; // correct: 10
cout << add2_loop(20, -9);
cout << " "; // correct: 11
cout << add2_loop(-7, -5);
cout << " "; // correct: -12
show_test(4, "add2", recursive);
cout << add2_recurse(4, 5);
cout << " "; // correct: 9
cout << add2_recurse(-5, 15);
cout << " "; // correct: 10
cout << add2_recurse(20, -9);
cout << " "; // correct: 11
cout << add2_recurse(-7, -5);
cout << " "; // correct: -12
cout << endl;

show_test(5, "mult2", functional);
cout << mult2_fx(2, 5);
cout << " "; // correct: 10
cout << mult2_fx(-4, 5);
cout << " "; // correct: -20
cout << mult2_fx(3, -10);
cout << " "; // correct: -30
cout << mult2_fx(10, 4);
cout << " "; // correct: 40
show_test(5, "mult2", looping);
cout << mult2_loop(2, 5);
cout << " "; // correct: 10
cout << mult2_loop(-4, 5);
cout << " "; // correct: -20
cout << mult2_loop(3, -10);
cout << " "; // correct: -30
cout << mult2_loop(10, 4);
cout << " "; // correct: 40
show_test(5, "mult2", recursive);
cout << mult2_recurse(2, 5);
cout << " "; // correct: 10
cout << mult2_recurse(-4, 5);
cout << " "; // correct: -20
cout << mult2_recurse(3, -10);
cout << " "; // correct: -30
cout << mult2_recurse(10, 4);
cout << " "; // correct: 40
cout << endl;

int primes[]{2, 3, 5, 7, 11, 13, 17}; // some prime numbers to search for
int size_primes = sizeof(primes) / sizeof(int);

show_test(6, "search", looping);
cout << search_loop(primes, size_primes, 2) << ", ";
cout << search_loop(primes, size_primes, 13) << ", ";
cout << search_loop(primes, size_primes, 10);
show_test(6, "search", recursive);
cout << search_recurse(primes, size_primes, 2) << ", ";
cout << search_recurse(primes, size_primes, 13) << ", ";
cout << search_recurse(primes, size_primes, 10) << endl;

// uncomment the next line for crash and error message...
// infinite_recursion();

cout << "\n...end\n";

return 0;
} // end of main

Sample Output Screenshots:

clang++-7 -pthread -std=c++17 -o main main.cpp >./main start... x 11) show_1_to_n (looping) : 1r) show_1_to_n (recursive) : 1 2 3 4 5 6 7 1 2 3 4 5 6 7 21) show_n_to_1 (looping): 2r) show_n_to_1 (recursive) : 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 31) reverse (looping): 3r) reverse (recursive): desserts desserts 4f) add2 (functional): 9 10 11 -12 41) add2 (looping): 9 10 11 -12 4r) add2 (recursive) : 9 10 11 -12 5f) mult2 (functional): 10 -20 -30 40 51) mult2 (looping): 10 -20 -30 40 5r) mult2 (recursive) : 10 -20 -30 40 61) search (looping): 0, 5, -1 6r) search (recursive): 0, 5, -1 ...end

Hope it helps, if you like the answer give it a thumbs up. Thank you.