**Lab 21: Recursion** | COMP1633 @ MRU

This lab is all about recursion! Click here for more info about recursion.

Now that that’s out of the way… for each of the following exercises, think about:

What is the base case?
What is the recursive case?
How is the problem reduced?

Numeric Exercises

Write a recursive function to display a decimal integer (i.e. base 10) in binary notation.
```
void show_as_binary (int n);
```
The iterative solution to this function might be something like:
```
void show_as_binary (int n) {
    int bit = 0;
    string bin = "";
    while (n > 0) {
        bit = n % 2;
        n /= 2;
        bin = to_string(bit) + bin;
    }
    cout << bin;
}
```
However, the recursive solution does not need a string accumulator - you can cout the bits directly.
Since this exercise doesn’t have a bunch of dependencies, I can just test the first problem. However, I recommend you attempt the rest to try to wrap your head around recursion - particularly since we have an exam coming up soon!
As usual, cd up to your top-level labs folder and run:
```
make lab=recursion
```

The mathematical operation “n choose r” denotes all ways of choosing r elements from a set of n elements where n ≥ r. For example:

Expression	Result	Explanation
4 choose 4	1	there is 1 way of choosing 4 items from a set of 4 (take them all!)
4 choose 1	4	there are 4 ways of choosing 1 item from a set of 4 (pick one!)
4 choose 2	6	there are 6 ways to choose 2 – try it
4 choose 3	4	there are 4 ways to choose 3 – try it

Write a recursive function called choose which takes as input two integers, n and r, and returns the number of possible ways of choosing.

Hints:

To choose 3 marbles from a collection of 5, decide if the first marble is “in” (part of the chosen set) or “out”. If it is “in” then recursively choose 2 more from a collection of 4. If it is “out” then recursively choose 3 from a collection of 4. Combine these two scenarios to form the recursive case.
Notice that both n and r are shrinking toward values for which the answer is directly available. Therefore there are two base cases.

Linked List Exercises

For each of these problems, define a Node as follows (or just copy the linkedlist lab, it’s the same Node structure):

struct Node {
    int data;
    Node *next;
};

Create a linked list to test your functions. You’ll probably find this easiest by defining a function, e.g.:

void add_to_front(Node *&head, int data) {
    Node *new_node = new Node;
    new_node->data = data;
    new_node->next = head;
    head = new_node;
}

Write a recursive function to find a given target number in the list:
```
Node *find_target(Node *head, int target);
```
Don’t assume the list is sorted! Be sure to identify all base cases and recursive cases during the algorithm design.
Write a recursive function which will determine whether two linked lists are equal. Two lists are equal if they contain the same number of nodes, and if each corresponding pair of nodes contains the same value.
```
bool equal_lists (Node *head1, Node *head2);
```