📖
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
  • Reverse a String Recursively
  • Tracing Example
  • Switching the order
  • Try This Example
  1. 6. Recursion
  2. 6.1 Functional Recursion

6.1.3 Recursion Example: Reverse String

Take a look at another example, this time with a string. The problem you are trying to solve is to print a string in reverse order.

From your knowledge of loops, you should know that you can print a string in reverse order using a loop, for example:

string str = "hello";

for (int i = str.size() - 1; i >= 0; i--) {
    cout << str[i];   
}

Output:

olleh

This problem can also be solved recursively. Recursion is another form of an iterative statement and you will find that many recursive problems can be rewritten with a for or while loop.

Reverse a String Recursively

In the problem below, notice that the base case when the string length is less than or equal to 1. When the string only has a length of 1, it is the same backward and forwards. The same could be said for a length of 0. Either scenario works for a base case, however, if you do want to consider the case of an empty string, you must cover zero in your base case.

When you are in your base case, you can simply print the string since it is the same backward and forwards.

When you are not in the base case, your recursive call should be to a string one smaller than the current string and then print the first letter.

Tracing Example

Take a look at how this would work if the user entered hello.

The first call from main would be:

  • reverse("hello") - Not the base case, so the return will call reverse("ello"). Notice that the return statement will add the letter h after the recursive call returns.

  • reverse("ello") - Not the base case. Calls reverse("llo").

  • reverse("llo") - Not the base case. Calls reverse("lo").

  • reverse("lo") - Not the base case. Calls reverse("o").

  • reverse("o") - Base case. Returns o to reverse("lo"). Remember this will be the first letter in the return string since all others are waiting on the recursive call to finish.

  • reverse("lo") returns the o + the l to reverse("llo").

  • reverse("llo") returns the ol + the other l to reverse("ello")

  • reverse("ello") returns oll + the e to reverse("hello")

  • reverse("hello") returns olle + the h to the main function, which then prints the string reversed.

Switching the order

One of the things that is really nice about recursion is that a small change can be made to the program to get very different results. In this example, try switching the order of the recursive call and the substring from:

return reverse(s.substr(1)) + s.substr(0,1);

to

return s.substr(0,1) + reverse(s.substr(1));

This small change will have a noticeable impact on the code. How could a small change like this impact some of the data structures you have seen?

Previous6.1.2 Basic Recursive Problem: ExponentialNext6.1.4 Recursion Example: Make Sum

Last updated 3 years ago

Try This Example