đź“–
C++
  • 1. C++ Basics
    • 1.1 Input, Output, and Program Structure
      • 1.1.1 Welcome to Data Structures in C++
      • 1.1.2 Hello World
      • 1.1.3 Input and Output
      • 1.1.4 getline and cin
      • 1.1.5 Program Structure
    • 1.2 Basic Data Types
      • 1.2.1 Basic Data Types
        • 1.2.1.1 Differences between C++ and Java Data Types and Variables
      • 1.2.2 Strings and Characters
      • 1.2.3 Numbers
      • 1.2.4 Booleans
    • 1.3 Conditional Statements
      • 1.3.1 Conditional Statements
      • 1.3.2 Basic If/Else Statements
      • 1.3.3 Comparing Strings
      • 1.3.4 Logical Operators
    • 1.4 Loops
      • 1.4.1 Loops
      • 1.4.2 For Loops
      • 1.4.3 While Loops
      • 1.4.4 Searching a String
    • 1.5 Functions in C++
      • 1.5.1 Functions in C++
      • 1.5.2 Defining and Calling Functions
      • 1.5.3 Passing by Reference vs Value
      • 1.5.4 Function Prototypes
  • 2. Going Beyond the Basics
    • 2.1 Vector Basics
      • 2.1.1 Vector Basics
      • 2.1.2 Creating and Accessing Vectors
      • 2.1.3 Inserting into a Vector
      • 2.1.4 Looping Through a Vector
    • 2.2 Function Default Values
      • 2.2.1 Function Default Values
      • 2.2.2 Default Values
      • 2.2.3 Default Values with a Prototype
      • 2.2.4 Example: Splitting a String
    • 2.3 Structs
      • 2.3.1 Structs
      • 2.3.2 Defining and Accessing Structs
      • 2.3.3 Using Structs: Line Length
    • 2.4 File Input/Output
      • 2.4.1 File Input/Output
      • 2.4.2 Reading in a File
      • 2.4.3 Processing a File
      • 2.4.4 Writing to a File
      • 2.4.5 Creating an Input Stream from a String
    • 2.5 Error Handling
      • 2.5.1 Error Handling
      • 2.5.2 Validating a Number
      • 2.5.3 Validating a Vector Index
      • 2.5.4 Throwing Other Values
  • 3. Libraries
    • 3.1 Header Files
      • 3.1.1 Header Files
      • 3.1.2 Header File
      • 3.1.3 Header and Implementation File
      • 3.1.4 Safer Header
    • 3.2 Using Libraries
      • 3.2.1 Using a Utilities Library
      • 3.2.2 The Util Library
  • 4. 2D Vectors, Stacks, and Queues
    • 4.1 2D Vectors
      • 4.1.1 2D Vectors
      • 4.1.2 The 2D Vector
      • 4.1.3 Creating a 2D Vector
    • 4.3 Stacks
      • 4.3.1 Stacks
      • 4.3.2 Basic Stack
      • 4.3.3 Stack Example: Reverse a String
    • 4.5 Queues
      • 4.5.1 Queues
      • 4.5.2 Basic Queues
      • 4.5.3 Queue Example: Next in Line
  • 5. Sets and Maps
    • 5.1 Pairs and Iterators
      • 5.1.1 Pairs and Iterators
      • 5.1.2 Pairs
      • 5.1.3 Iterators
    • 5.3 Sets
      • 5.3.1 Sets
      • 5.3.2 Basic Sets
      • 5.3.3 Iterating Through a Set
      • 5.3.4 Sets of Struct Values
    • 5.4 Maps
      • 5.4.1 Maps
      • 5.4.2 Map Basics
      • 5.4.3 Iterating Through a Map
      • 5.4.4 Updating Maps
  • 6. Recursion
    • 6.1 Functional Recursion
      • 6.1.1 Functional Recursion
      • 6.1.2 Basic Recursive Problem: Exponential
      • 6.1.3 Recursion Example: Reverse String
      • 6.1.4 Recursion Example: Make Sum
    • 6.2 Procedural Recursion
      • 6.2.1 Procedural Recursion
      • 6.2.2 Print Binary
      • 6.2.3 Print Permutations
      • 6.2.4 Depth vs Breadth Search
  • 7. Pointers, Linked Lists, and Graphs
    • 7.1 Pointers
      • 7.1.1 Pointers
      • 7.1.2 Assigning and Updating Pointers
      • 7.1.3 Pointers and Functions
      • 7.1.4 Pointers and Data Structures
    • 7.2 Linked Lists
      • 7.2.1 Linked Lists
      • 7.2.2 Basic Linked List
      • 7.2.3 Linked List and Recursion
      • 7.2.4 Example: Sorted Phone Book
      • 7.2.5 Doubly Linked List
    • 7.3 Graphs
      • 7.3.1 Graphs
      • 7.3.2 Basic Example: Breadth First Search
      • 7.3.3 Application: Connecting Cities
Powered by GitBook
On this page
  • Base Case
  • Recursive Call
  • Walk Through Example
  • Kickoff Function
  • Try This Example
  1. 6. Recursion
  2. 6.2 Procedural Recursion

6.2.3 Print Permutations

In this example, you will have an opportunity to take a look at a more detailed, but common recursive problem: Permutations.

Recall that permutations take a set of values and prints out all the possible sequences of the values. In this case, this example takes a list of letters and prints out all the combinations to get to a specific length.

Example: Given a set of values[A, B, C] what are all the 2 character permutations?

AB
AC
BA
BC
CA
CB

Base Case

What is the base case? In this case, the base case will be when we get a string that has the same length as our target length. Until you get there, you will keep adding letters. Since this is a procedural recursive function, once you get to your base case, you will print out the results.

Recursive Call

To accomplish this task, the function will actually make several recursive calls from a for loop. Take a look at the header of this example:

void permute(string soFar, string rest, int length)

Notice that the header has two strings, soFar and rest. The soFar string represents the current permutation that is being built. This is the one that gets checked against the length to meet the base case.

rest holds all the remaining letters that have not been put into the soFar string. To create the permutation, you will add each one of the letters from the rest string to the soFar string one at a time. After you add one, you remove it from rest and make the recursive call with the expanded soFar and the shrunken rest.

Walk Through Example

Take a look at this walk through using the [A, B, C] and length of 2 that you saw above.

When the function is first called, soFar is empty and rest contains ABC.

The base case is not met, so you loop through each of the letters in rest. On the first pass of the loop, A is added to soFar and then called recursively with rest containing BC. The second pass calls B with AC and then the third pass calls C with AB.

In the next round, there are the three recursive calls from above. In all three calls, the base case is still not met, so the program loops. In the first call above, B is added to A to create a soFar of AB and then it is called recursively with a rest of C. The second loop of that first call sees a soFar of AC and a rest of B.

Each of those two recursive calls will meet the base case since the soFar string is now a length of two. They then print out AB and AC respectively, and make no more recursive calls.

Similar recursive calls are made for the second round with the B and C recursive calls. In total, 6 recursive calls are being made.

Kickoff Function

This example also uses a kickoff function. As mentioned before, the idea behind the kickoff function is that it can hide the implementation details that the user doesn’t really need to know. All they need to do is specify the list of available letters and the string length. They don’t need to know that there is a soFar and rest string.

Previous6.2.2 Print BinaryNext6.2.4 Depth vs Breadth Search

Last updated 3 years ago

Try This Example