Recursion in C++

A lab entirely about solving problems via recursive practices.

About

For this lab, you are charged with completing the provided recursion.cpp file. Using this README as your guide, you will start from relatively simple problems, and work your way up to more complex use cases for recursion.

Recursion itself is a method of programming where the problem is reduced until it has a trivial solution, which is then propagated back through the recursive calls to arrive at the final solution.

Submitting your code

Please submit your recursion.cpp file to Mimir.

Level 0: List Summation

The first task in this lab is to sum all elements of a provided list. For example:

int arr[] = {1, 2, 3, 4, 5}; int s = sum_arr(arr, 5); // Length gets passed because int arrays don't know their own length! std::cout << s << std::endl; // Prints 15 to the command line.

The crux of this problem is that we know how to add 2 numbers together, and we also know that the sum of 1 number is itself; but, when presented with n numbers, we must somehow reduce the number of elements to either 1 or 2.

If we were to expand the above example, it may read something like:

Hint 1: This problem can be represented as follows: 5 + (4 + (3 + (2 + (1)))) or arr[n-1] + (arr[n-2] + (arr[n-3] + (arr[n-4] + (arr[n-5])))) where n is the size of the array.

Level 1: Palindrome Testing

A palindrome is a string that reads the same both forwards and backwards, such as "abcba". To test if a given string is a palindrome, you can ask: is there only one character? If so, the answer is yes, since "a" is still "a" in reverse. Second, you may ask: is the first character equal to the last character? If so, continue traversing the string until there is just one character left.

This process of narrowing the problem down until there is either one or zero characters left, is recursion!

In your recursion testing you will use three variables, the character array string, left, and right. Left and right represent the indexes of the first and last element. In other words, given: "abcba", left will initially be 0, right will initially be 4.

Hint 1: Do a few test runs by hand, try and formulate a plan before putting down any code. Hint 2: If the characters at indexes left and right are not equal, then it is not a palindrome.

Level 2: Min / Max Finding

For this level you must complete both functions, one for finding the minimum of any given list, the other to find the maximum. For these problems you may create a helper function, but you must have your recursive call in the pre-declared function.

Some useful helpers have already been declared in the .cpp file, namely int min and int max; these functions receive two integers, and return the smaller or greater of the two.

Hint 1: Examine the pattern you uncovered in level 0, the same pattern can be found here.

Level 3: Multiplication

Multiply two numbers together, without using the * operator.

Hint 1: Think about how multiplication works, and how you can use other mathematical operations to replicate that effect.

Level 4: Printing a triangle

To pass level three, you must write a function to print triangles to std::cout that takes three positive integers: a, b, and c as input. The function should print the '+' character a times, then a + c times, then a + c + c times, and so on. This pattern should repeat until the line is b characters long. At which point, the pattern is repeated backwards. For example, calling draw_triangle(4, 7, 1) will output:

++++ +++++ ++++++ +++++++ +++++++ ++++++ +++++ ++++

In order to test this function, you will output (<<) the characters to the parameter os. The only reason why this is necessary, is for unit testing.

Don't forget to pass the os object in your recursive calls, or you will fail Mimir!

Hint 1: The order of the recursive call is the most important part about this level. Hint 2: Consider what you would write if you were tasked with printing two lines of a characters at each call, in order to draw a staircase. The code you write for this task will be eerily similar to the one you write to draw triangles! Hint 3: If you've figured out how to draw stairs of characters two lines wide, then take a deeper look at where the recursive call is placed, and see if moving that call can change the order of printing!

STARTER CODE:

/** This is where to do your work.

*

*/

#include

#include "recursion.h"

bool is_palindrome(const char *string, int left, int right) {

// Remove these lines before you start coding.

(void) string;

(void) left;

(void) right;

return false;

}

int arr_sum(int *arr, int n) {

// Remove these lines before you start coding.

(void) arr;

(void) n;

return 0;

}

int min(int a, int b) {

// Remove these lines before you start coding.

(void) a;

(void) b;

return 0;

}

int arr_min(int *arr, int n) {

// Remove these lines before you start coding.

(void) arr;

(void) n;

return 0;

}

int max(int a, int b) {

// Remove these lines before you start coding.

(void) a;

(void) b;

return 0;

}

int arr_max(int *arr, int n) {

// Remove these lines before you start coding.

(void) arr;

(void) n;

return 0;

}

void draw_triangle(int a, int b, int c, std::ostream &os) {

// The ostream is only for testing, instead of using "std::cout", please use "os <<"

// Remove these lines before you start coding.

(void) a;

(void) b;

(void) c;

return;

}

int multiply(int a, int b) {

// Remove these lines before you start coding.

(void) a;

(void) b;

return 0;

}