A summation can be broken down into smaller chunks but using the same structure as the original.

Let's say we have \[ \sum_{i=1}^{6} { i } = 1 + 2 + 3 + 4 + 5 + 6 \]

The summation can be redefined recursively:

\[ \sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i } \]

The summation from \(i = 1\) to \(6\) is equivalent to whatever the sum is at \(i=6\), plus the sum from \(i = 1\) to \(5\).

We can continue this way until we get to a case that we know (e.g., \(\sum_{i=1}^{1} { i }\)).

• \(\sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i }\)
• \(\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i }\)
• \(\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i }\)
• \(\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i }\)
• \(\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i }\)
• We know that \(\sum_{i=1}^{1} { i } = 1\), then we move back up to sub out this value.

Now we start substituting this value back for each step…

With a factorial of \(n\), written \(n!\) the formula to solve this is:

\[ n! = n \cdot (n-1) \cdot ... \cdot 3 \cdot 2 \cdot 1 \]

So,

• \(2!\) is \(2 \cdot 1\),
• \(3!\) is \(3 \cdot 2 \cdot 1\),
• \(4!\) is \(4 \cdot 3 \cdot 2 \cdot 1\), and so on.

Additionally, we can break down each of these equations: \(3!\) is equivalent to \(3 \cdot 2!\) \(4!\) is equivalent to \(4 \cdot 3!\) … \(n!\) is equivalent to \(n \cdot (n-1)!\)

Thinking of breaking down the problem here in this way is looking at it recursively.

Try to convert the Summation function to be recursive. Think about what the terminating case would be and the recursive case. Use the Factorial function for reference.

Summation - Iterative solution

int SumI( int n )
{
    int result = 0;
    for ( int i = 1; i <= n; i++ )
    {
        result += i;
    }
    return result;
}

Summation - Recursive starter

int SumR( int n )
{
    // Terminating case?
    // Recursive case?
}

Summation - Recursive solution

int SumR( int n )
{
    if ( n == 1 ) { return 1; }  // Terminating case
    return n + SumR( n-1 );      // Recursive case
}

Now let's make a function that will draw a line of symbols, with a parameter being the length. Iteratively, it could look like this:

DrawLine - Iterative solution

void DrawLineI( int amount )
{
    for ( int i = 0; i < amount; i++ )
    {
        cout << "-";
    }
}

How would we repeat this behavior recursively? How do we have a "count up" sort of functionality? What would be the terminating case?

We're going to think of it a little differently: The recursive function will only output one "-" before it recurses. Each time it recurses, it draws one more dash…

DrawLine - Recursive work in progress

void DrawLine_Recursive( int amount )
{
    cout << "-";
    // Recursive case
    DrawLineR( amount );
}

However, we don't have a terminating case… it will continue looping, but it won't go forever like a bad while loop. We will eventually run out of stack space and the program will encounter a stack overflow and end.

So what would the terminating case be? How do we adjust the amount each time? Since amount is the one parameter we have, let's have the recursion stop once it is 0. Each time we recurse, we can pass in amount-1 to the next call…

DrawLine - Recursive solution

void DrawLine_Recursive( int amount )
{
    cout << "-";

    // Terminating case
    if ( amount == 0 ) { return; }

    // Recursive case
    DrawLineR( amount - 1 );
}

How can we write a function that takes a start and end integer, and outputs each number between them (including the start and end)?

Iteratively, it could look like this:

CountUp - Iterative solution

void CountUpI( int start, int end )
{
    for ( int i = start; i <= end; i++ )
    {
        cout << i << "\t";
    }
}

CountUp - Recursive starter

Try to fill in this function to build a recursive solution:

void CountUpR( int start, int end )
{
}

CountUp - Recursive solution

void CountUpR( int start, int end )
{
    cout << start << "\t";

    // Terminating case
    if ( start == end ) { return; }

    // recursive case
    CountUp_Recursive( start+1, end );
}

On a harddrive, we generally have files and folders. Folders can contain files, but they will also contain subfolders as well. And subfolders can each contain their own subfolders.

When you don't know the exact layout of the filesystem, how would you even begin to iteratively search for a specific file?

Instead, it is good to think of it recursively. For example, say we're searching for a folder where you store your Recursion homework. We will begin searching at the top-most folder of the computer. The algorithm would then run like…

Let's say we have a recursive function, Find( FOLDERNAME, currentFolder ).

For this functionality, terminating cases would be:

• Have we found the item? Return it.
• Are we out of places to search? Return nothing.

And the recursive case would be:

• Has a subfolder? Call Find() on that folder.

So looking at an example set of folders and files like this:

C:
|-- games/
|   |--DOOM.exe
|-- school/
|   |-- cs210/
|   |-- cs235/
|       |-- recursion.txt
|-- work/
    |-- TPSreports/

So steps to locate the "Recursion" folder would look like this:

Find( "recursion.txt", "C:" )
Does "C:" have the recursion.txt file? NO...
Does it have subfolders? YES... OK, Recurse.
|
|  Find( "recursion.txt", "C:\games" )
|  Does "C:\games" have the recursion.txt file? NO...
|  Does it have subfolders? YES... OK, Recurse.
|  |
|  |  Find( "recursion.txt", "C:\games\DOOM.exe" )
|  |  Does "C:\games\DOOM.exe" match "recursion.txt"? NO...
|  |  Does it have subfolders? NO... Return.
|  |
|  Does "C:\games" have any more subfolders? NO... Return.
|
Does "C:" have any more subfolders? YES... OK, Recurse.
|
|  Find( "recursion.txt", "C:\school" )
|  Does "C:\school" have the recursion.txt file? NO...
|  Does it have subfolders? YES... OK, Recurse.
|  |
|  |  Find( "recursion.txt", "C:\school\cs210" )
|  |  Does "C:\school\cs210" have the recursion.txt file?
|  |  NO... Does it have subfolders? NO... Return.
|  |
|  Does "C:\school" have any more subfolders? YES... OK, Recurse.
|  |
|  |  Find( "recursion.txt", "C:\school\cs235" )
|  |  Does "C:\school\cs235" have the recursion.txt file? *YES*...
|  |  OK, return this path.
|  |
|  "C:\school\cs235" path was returned, continue returning it.
|
"C:\school\cs235" path was returned, continue returning it.

And the result for finding the recursion folder is "C:\school\cs235".

Solving a maze can be approached from a recursive standpoint much easier than an iterative one.

Terminating cases:

1. If we get to the end of the maze, SUCCESS.
2. If we hit a dead-end, GO BACK (return).

Recursive case: Explore each available direction, except the direction you came from.

1. Try to go NORTH
2. Try to go EAST
3. Try to go SOUTH
4. Try to go WEST

Example step-through, going from A to B (@) is current location.

  ########   Path so far:
  ### ## #   Recursive case: Can't go NORTH, can go EAST...
A @   ##  Z
  ###    #
  ########

  ########   Path so far: E
  ### ## #   Recursive case: Can't go NORTH, can go EAST...
A  @  ##  Z
  ###    #
  ########

  ########   Path so far: E E
  ### ## #   Recursive case: Can't go NORTH, can go EAST...
A   @ ##  Z
  ###    #
  ########

  ########   Path so far: E E E
  ### ## #   Recursive case: Can go NORTH...
A    @##  Z
  ###    #
  ########

  ########   Path so far: E E E N
  ###@## #   Recursive case: Can't go NORTH, can't go EAST,
A     ##  Z  can't go WEST...
  ###    #   Return to previous location...
  ########

  ########   Path so far: E E E
  ### ## #   Recursive case: Already went NORTH.
A    @##  Z  Can't go EAST... Can go SOUTH...
  ###    #
  ########

  ########   Path so far: E E E S
  ### ## #   Recursive case: Can go EAST...
A     ##  Z
  ###@   #
  ########

  ########   Path so far: E E E S E
  ### ## #   Recursive case: Can go EAST...
A     ##  Z
  ### @  #
  ########

  ########   Path so far: E E E S E E
  ### ## #   Recursive case: Can go EAST...
A     ##  Z
  ###  @ #
  ########

  ########   Path so far: E E E S E E E
  ### ## #   Recursive case: Can go NORTH...
A     ##  Z
  ###   @#
  ########

  ########   Path so far: E E E S E E E N
  ### ## #   Recursive case: Can go NORTH...
A     ##@ Z
  ###    #
  ########

  ########   Path so far: E E E S E E E N N
  ### ##@#   Recursive case: Can't go NORTH, can't go EAST,
A     ##  Z  can't go WEST.
  ###    #   Return to previous location...
  ########

  ########   Path so far: E E E S E E E N
  ### ## #   Recursive case: Can go EAST...
A     ##@ Z
  ###    #
  ########

  ########   Path so far: E E E S E E E N E
  ### ## #   Made it to the end!
A     ## @Z  Return "EEESEEENE" as the solution!
  ###    #
  ########