📖
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
  • Moving To a Simple Problem
  • Finding the Base Case
  • Recursive Call
  • Try This Example
  1. 6. Recursion
  2. 6.1 Functional Recursion

6.1.2 Basic Recursive Problem: Exponential

Previous6.1.1 Functional RecursionNext6.1.3 Recursion Example: Reverse String

Last updated 3 years ago

The basic premise behind recursion is that you want to simplify your problem until you get to the simplest case possible. Each recursive call should make a step towards the simplest case.

Moving To a Simple Problem

Let’s take a look at an example of how you can take a problem and simplify it. Factorial is a good place to start.

Recall that the factorial of a number is the product of that number and all the positive numbers below. For example, 4 factorial (4!) is equal to 4 * 3 * 2 * 1.

Likewise, 3! is equal to 3 * 2 * 1. 2! is equal to 2 * 1, etc.

You should notice a pattern:

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

To solve 4!, you can simply multiply 4 by 3!. To find 3!, you can call the same function that you called for 4!, but using the number 3 in your call. You keep doing this until you reach your base case.

The base case is the simplest version of the problem. Once you reach the base case, you can hardcode a solution and return it to the previous functional call. The base case is where the recursive calls stop and without a base case, you may create an infinite loop.

In this case, your base case is when you calculate 1 factorial, which is simply just 1.

Example: Take a look at this example as a function. Notice that the function has a name factorial and it gets called from the main function as factorial(4).

The base case is represented on lines 6-8, when num equals 1.

When the value of num is greater than 1, it makes a recursive call to factorial(num - 1) on line 10. You will notice on the right of the example how the recursive calls keep growing until that base case is reached.

Once the base case is reached, each recursiveCall value is populated from the function return statement, then that function call can be satisfied and returned to the next function.

1 is returned to the factorial(2) call. Then 2 * 1 is returned to the factorial(3). 3 * 2 is then returned to the factorial(4) call, and finally, 4 * 6 is returned to the main function.

Finding the Base Case

One of the challenges of recursion is finding the base case. Finding the simplest case may not always jump out at you, but here are a few things to consider.

  • Oftentimes the base case for mathematical problems is zero or one. You can start by looking at solving that problem.

  • When looking at other things such as strings or sequences, you still want to think about zero or one, but now it is the length of a string. You will see an example of this in the next example.

  • Sometimes, there may be more than one base case. You will see this is especially true when looking at solving puzzles, as there will be a success base case and a fail base case.

Recursive Call

If you do not meet your base case criteria, then you make a recursive call. For a functional recursive problem, oftentimes your recursive call is put in your return statement.

The one rule to follow with the recursive call is that each call should take you at least one step closer to the base case.

Try This Example