Announcements

Professor Russell wishes to alert the class that he has uploaded an explanation for one of the recursive examples covered during lecture (firstNegative) on his website, located here.

Today's agenda:

Review of recursion.
A fair amount of practice.
Go over Homework 1 and Project 2 (with hints!).
Try to finish a bit early to have a mini homework lab.

Recursion

Recursion is just one of those iconic elements of computer science that takes a rather large paradigm shift to learn.

Not only is recursion useful, and can often simplify otherwise messy code, but it is the butt of many CS jokes; even Google is in on it:

Recursion is a little difficult to wrap your head around at first, but it will quickly feel like second nature.

Let's start with some definitions and facts:

Recursion is the repeated application of a recursive process; less formally, in CS, it is when a function calls itself.

Recursion vs. Iteration: Any process that can be written using recursion can be written using iteration, and vice versa. However, while it may be computationally faster to use iteration, sometimes the code is untenable and a much simpler recursive solution exists.

Reasons for Using: Typically, we use recursion to take a large problem that is difficult to solve, break it into some number of small problems that are easy to solve, and then combine our mini-results into a result that solves the original large problem!

Usually, this splitting of a problem involves two key cases:

The Base Case or stopping condition, is when we've split our problem into a sufficiently small one that we can trivially solve. We return a solution to our small problem in the base case(s) and do not recurse further.

The Recursive Case(s) are when we have not reached a small enough subproblem to solve and need to continue looking for a base case that is trivially solved. In these cases, we call our function from within our function on some even smaller problems.

Now, there are some constraints on valid recursive functions:

Recursive functions must have some stopping condition lest they recurse infinitely.
Each recursive case must bring the problem closer to a base case or solution; if they diverge, then we're not guaranteed that the recursion will successfully terminate.

Let's start off gently, shall we?

First & Rest Splits

When we talk about solving smaller subproblems, we don't always have to think about performing massive splits on our data set to achieve our goal.

First and rest splits (or linear recursion) reduces the size of the input by a linear amount with every recursive step (e.g., reducing the size of an input array by 1 on each recursive call).

For our first example, we'll focus on an array of ints.

Create a recursive function sum that returns the sum of an array of ints.

Let's use the following overly-parameterized function signature for sum (that we'll simplify later):

  int sum (const int arr[], int size, int total);

Here, I have an int array arr, the number of elements remaining in it (size), and the running total of the elements' sum.

My strategy is to look at the first element in my current sub-list, add it to my total, then recurse on the rest of the list!

What is my base case in this scenario?

Since I'm summing all of the elements, my base case is when I've summed the last element and have run out of list items! i.e., size will be 0.

As soon as I hit my base case, I want to return the solution that I've collected.

Here's a function skeleton to get us on our way:

  int sum (const int arr[], int size, int total) {
      // [!] Base case check
      if ( ... ) {
          // [!] Return solution
          return ...;
      }
      // [!] Recursive case; go to next element, dec
      // size, and then add the current front to total
      return sum( ... );
  }

Click for solution...

  int sum (const int arr[], int size, int total) {
      // [!] Base case check
      if (size <= 0) {
          // [!] Return solution
          return total;
      }
      // [!] Recursive case; go to next element, dec
      // size, and then add the current front to total
      return sum(arr + 1, size - 1, total + *arr);
  }

With this implementation in mind, trace the stack frames of the following call to sum:

  int i[] = {1, 3, 6};
  cout << sum(i, 3, 0) << endl;

Yeah I haven't mastered the whole gif thing yet so... enjoy all that whitespace above...

Note: Whenever a recursive call is made, I suspend my position in the current stack frame until the ones above it return.

See how that works?

Tricks with Recursive Returns

One of the biggest hurdles with learning recursion is realizing that solutions need not be stored in a single variable (like the total parameter in the example above), but rather, can be built up in each stack frame's return values.

This will typically look like a recursive call of the format: return something + recursiveCall(...);

Now, let's try a fancier version of sum that does not rely on the crutch of the total parameter:
int sum (const int arr[], int size)

Here's another function skeleton to get us on our way:

  int sum (const int arr[], int size) {
      // [!] Base case check
      if (size == 0) {
          return 0;
      }
      // [!] Recursive case
      return ...;
  }

Click for solution...

  int sum(const int arr[], int size) {
      // [!] Base case check
      if (size == 0) {
        return 0;
      }
    
      // [!] Recursive case
      return *arr + sum(arr + 1, size - 1);
  }

Divide & Conquer Splits

Divide & conquer splits attempt to reduce the size of the problem by some factor (e.g., into 2 halves) with each recursive call.

Unlike the first & rest split, we will attempt to substantively reduce the size of each subproblem, solve the trivial case, and then recombine to the larger problem.

Later in the course, we'll see algorithms that rely upon divide-and-conquer splits to improve efficiency, but for now, we'll look at a simple example that demonstrates the mechanics.

Here's a preview of the mergesort algorithm, which divides a list of values into smaller and smaller sub-lists until they are of size 2, and it is easy to determine if the 2-element lists are already sorted or should be switched (which is then done upwards until the list is reconstructed).

We'll look at this algorithm later in the course, but here's a preview:

  void sort (int a[], int b, int e) {
      if (e - b >= 2) {
          int mid = (b + e) / 2;
          
          // Recursive call on first half of a
          sort(a, b, mid);
          // Recursive call on other half of a
          sort(a, mid, e);
          
          // Merge those sorted subpropblems!
          merge(a, b, mid, e);
      }
  }
  
  int main () {
      int arr[] = {4, 3, 1, 2};
      sort(arr, 0, 4);
      // arr will now be {1, 2, 3, 4}
  }

There's a big step of understanding how this works, and it's under the assumption of a working merge function:

Here, the merge function combines the two sublists into a single, ordered sublist.

Let's take a look at it in action (gif shamelessly stolen from Wikipedia):

Indirect Recursion

Indirect Recursion is a recursion style where some function A calls another function B which then calls A again. It is sometimes referred to as "mutual recursion."

We typically use indirect recursion when:

It is simpler to delegate one part of the recursive process to one method (say, A), and a separate part to another (say, B).
When a programming language does not support recursion, but we want recursive behavior.

You might find this approach useful for your upcoming Project 2, but for now, here's a simple example, taken shamelessly from this article, with other good recursion materials:

  bool isEven(int no)
  {
      // Base case
      if (0 == no)
          return true;
      // Recursive case
      else
          return isOdd(no - 1);
  }
  
  bool isOdd(int no)
  {
      // Base case
      if (0 == no)
          return false;
      // Recursive case
      else
          return isEven(no - 1);
  }

Calling the above with isEven(4) appears as:

Practice

Let's try some practice recursion problems!

When approaching your recursion solutions, keep the following guidelines in mind:

Start with your base cases, and then design your recursive cases with the starting arguments in mind -- think about how you can get from the start to your base cases!
Remember, where appropriate, you can modify your parameters in recursive calls to get closer to base cases.
To record-keep a solution as it's being formed, remember that you can get clever with return values like return something + recursiveCall(...);, where the + operator is only one of many options to use!

To test our solutions, we'll use a popular tool from the C++ assert library in the form of assert statements.

  #include <assert.h>
  // No, that's not a typo, it's really
  // <assert.h> with the .h
  
  // [!] Terminates the program if the argument
  // is false, does nothing otherwise
  assert(booleanExpression);

Cliche Recursion: Fibonacci Sequence

There's a rite of passage for all students of recursion: you must solve the Fibonacci problem.

The Fibonacci sequence begins with two 1's, and then continues with each digit being the sum of the two previous.

Compute the nth Fibonacci number in this sequence using a recursive function with signature: int Fibonacci(int n);

Here's a sample start of the Fibonacci sequence:

  // 1, 1, 2, 3, 5, 8, 13, 21, ...
  int main() {
      assert(fib(0) == 0);
      assert(fib(1) == 1);
      assert(fib(2) == 1);
      assert(fib(5) == 5);
      assert(fib(8) == 21);
      cout << "[!] Tests passed!" << endl;
  }

Here's a code skeleton:

  int fib(int n) {
      // Base cases:
      if (n == 0) { return ???; }
      if (n == 1) { return ???; }
      
      // Recursive case:
      return fib( ??? ) + fib( ??? );
  }

No more hand-holding, you can try the next ones yourselves!

Reversing Strings

Create a recursive function that takes a string as input and returns its reverse. Signature: string reverseString(string s);

  int main() {
      assert(reverseString("") == "");
      assert(reverseString("a") == "a");
      assert(reverseString("bat") == "tab");
      assert(reverseString("andrew") == "werdna");
      assert(reverseString("racecar") == "racecar"); // lol
      cout << "[!] Tests passed!" << endl;
  }

Max Int in List

Create a recursive function that takes in an array of ints, the size of the array, and returns the max int. Signature: int maxInt(int arr[], int size);

We'll make 2 simplifying assumptions:

You may assume that arr always has at least 1 element
You may use the #include >algorithm> library's max(a, b) function which returns the larger of ints a and b.

  int main() {
      int a[] = { 5 };
      int b[] = { 1, 5, 2 };
      int c[] = { 1, 17, 22, 90 };
      assert(maxInt(a, 1) == 5);
      assert(maxInt(b, 3) == 5);
      assert(maxInt(c, 4) == 90);
      cout << "[!] Tests passed!" << endl;
  }

Is an Int Prime?

Create a recursive implementation (no iteration) of a function that determines if the input int is prime or not. Signature: bool isPrime(int n);

Hint: create a helper method that has parameters that are conducive to a solution.

  int main() {
      assert(isPrime(2));
      assert(isPrime(3));
      assert(!isPrime(4));
      assert(isPrime(5));
      cout << "[!] Tests passed!" << endl;
  }

Is a String Symmetrical?

Create a recursive function to determine if a string is the same forwards as backwards. Signature: bool isSymmetrical(string s);

  int main() {
      assert(isSymmetrical(""));
      assert(isSymmetrical("a"));
      assert(isSymmetrical("aba"));
      assert(isSymmetrical("racecar"));
      assert(!isSymmetrical("mirror"));
      cout << "[!] Tests passed!" << endl;
  }

Does a String Contain A Sequence?

This one's a challenge! If you can figure it out, you're likely well equipped to embrace the homework.

Create a recursive function to determine if a target string is found *in sequence* within a container string. Signature: bool containsSequence(string container, string target);

  int main() {
      assert(containsSequence("cdaotg", "dog"));
      assert(containsSequence("cdaotg", "cat"));
      assert(!containsSequence("cdaotg", "catdog"));
      cout << "[!] Tests passed!" << endl;
  }

Homework Tips

In the upcoming Homework 1 and Project 2, you'll get ample time to practice your skills with recursion!

We'll take a look at each assignment now, and I'll give you a few tips that might help you think about each problem.

Homework 1

Homework 1 gives you a smattering of simple recursion exercises. Click here for the link!

Problem	Hint
mult	Consider manipulating only 1 of the parameters on every recursive call!
countDigit	Consider a linear recursion with "return tricks" like we did for sum above.
pairPlus	Same as hint above.
subParen	Consider "squeezing" the string down to the open and closed parens on each recursive call.
sumCombination	Consider an approach whose base case is that the total is reduced to 0 by subtracting combinations of the ints. You might find the string sequence example above inspirational...
pathExists	Consider trying all directions in a single recursive call (you'll see this in the pseudocode).

Project 2

Project 2 puts your recursion skills to the test, requiring you to build anagrams (words that can be formed from a set of letters) Click here for the link!

Hint:

Consider breaking the recursivePermute function down using mutual recursion.
In particular, consider having another function that "slides" each letter in the input string from the front to the back, and the main workhorse function does this for every letter.
Remember to make sure that you're not adding duplicates to the results!