## Question

For debugging purpose, you may add some printing statements within the recursive function to show what is happening within each function call. Here are two hints for you:

• Let the recursion talk to you by printing informative messages.

• Write routines to print each data structure, so you can easily see what is happening.

Task 1. Source file name: digitsum.cpp

Write a recursive method to determine the sum of the digits of a positive integer. For example, the sum of the digits of 51624 is 5 + 1 + 6 + 2 + 4 = 18. The function prototype is:

int computeSumOfDigits(int);

Task 2: Source file name: stair.cpp

You're standing at the base of a staircase and are heading to the top. A small stride will move up one stair, a large stride advances two. You want to count the number of ways to climb the entire staircase based on different combinations of large and small strides. For example, a staircase of three steps can be climbed in three different ways: via three small strides or one small stride followed by one large stride or one large followed by one small. A staircase of four steps can be climbed in five different ways (enumerating them is an exercise left to you).

Write a recursive function that takes a positive value as the number of stairs and returns the number of different ways to climb a staircase of that height taking strides of one or two stairs at a time. The function prototype is:

int countWays(int);

Task 3: Source file name: subset.cpp

Given a set of integers and a target number, your goal is to find the total number of subsets of those numbers that sum to the given target number. For example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the subset {3, 1} sums to 4 and the subset {7, -3} sums to 4. So the total number of subsets that sum to 4 is 2. On the other hand, if the target sum is 2, there is no subset that sums to 2. So the total number of subsetsthat sum to 2 is 0. The prototype for this recursive function is:

int countSubset(int [], int, int);

where the first parameter represents an array with several integers, the second parameter represents the number of elements in the array, and the third parameter represents the target number.

Task 4: Source file name: move.cpp

You have been given a puzzle consisting of a sequence of numbers, like this:

(3) 6 4 1 3 4 2 5 3 0

The parentheses on the initial number is a marker that can move to other numbers along the row. At each step in the puzzle, you may move the marker a number of steps indicated by the number it currently occupies. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker three steps to the right because there is no room to move three steps to the left. The goal of the puzzle is to move the marker to the number 0 at the far end of the sequence. In this configuration, you can solve the puzzle by making the following set of moves:

(3) 6 4 1 3 4 2 5 3 0 move 3 steps right

3 6 4 (1) 3 4 2 5 3 0 move 1 step left

3 6 (4) 1 3 4 2 5 3 0 move 4 steps right

3 6 4 1 3 4 (2) 5 3 0 move 2 steps right

3 6 4 1 3 4 2 5 (3) 0 move 3 steps left

3 6 4 1 3 (4) 2 5 3 0 move 4 steps right

3 6 4 1 3 4 2 5 3 (0) reach goal, stop

Even though this puzzle is solvable and indeed has more than one solution, some puzzles of this form may be impossible, such as the following one:

(3) 1 2 3 0

In this puzzle, you can bounce between the two numbers 3, but you cannot reach any other numbers.

Write a recursive function that takes a starting position of the marker along with an array containing several integers and the size of the array and returns true if it is possible to solve the puzzle from the starting configuration and false if it is impossible. You may assume that all the integers in the array are positive except for the last entry, the goal number, which is always zero. The values of the elements in the array must be the same after calling your function. The function prototype is:

bool isSolvable(int, int[], int) ;

where the first parameter represents the starting position of the marker, the second parameter represents the array with several integers, and the third parameter represents the number of elements in the array.

Task 5: Source file name: maze.cpp

Solve a 2-D maze read from a maze file (maze.txt), which consists of three segments: The first line contains the number of rows and columns in the maze. The second line contains the starting position of the explorer. The rest of the file contains the maze – one row per line. Walls are represented by ‘X’, paths are represented by ‘.’, and the treasure is represented by a ‘t’. Specifically, your recursive function should output a valid path between the treasure and the explorer. For example, here is an 11 × 10 maze with the explorer starting at the cell (9,4). Note: The most upper left cell location is (0, 0).

11 10

9 4

XXXXXXXXXX

XX...tX..X

XX.XXXX.XX

XX.......X

XXXXXXX.XX

X....XX.XX

X.XX.....X

X...XX.XXX

XXX..XXXXX

XXXX....XX

XXXXXXXXXX

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

int computeSumOfDigits(int);int main(int argc, char** argv) {

cout<<computeSumOfDigits(51624)<<"\n";

return 0;

}

int computeSumOfDigits(int n){

if (n <= 0) {

return 0;

}

return (n % 10) + computeSumOfDigits(n/10);

}...