đź“–
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
  • Multiple Base Cases
  • makeSum vs. solveSum
  • Explore This Example
  • Try This Example
  1. 6. Recursion
  2. 6.1 Functional Recursion

6.1.4 Recursion Example: Make Sum

In this example, you are going to explore a few more complicated recursion concepts.

The problem you are trying to solve is to determine if a combination of numbers can be put together to add up to a given sum.

For example, if given the numbers 4, 9, 3, 7, can you add up to 14? The answer would be yes, by using 4, 3, and 7.

With the same set of numbers, if asked to add up to 15, the answer would be no, since there is not a combination that can sum to 15.

Multiple Base Cases

When looking at this recursively, there are two base cases to consider. The first base case is a successful completion where our combination adds up to the desired output. The second base case is that you got to the end of the list without hitting the target.

if (sumSoFar == target) return true; // success
if (index == nums.size()) return false; // fail

The other thing that makes this problem interesting is that you need to consider more than one recursive call.

Determining whether there is a valid combination means that you need to look at all possible permutations. For example, in the above list, you cannot just consider the 4, then the 9 then the 3 because you would be over. The winning combination actually skips the 9.

So you should notice there are two recursive calls, one for including the next number and one for excluding the next number. By including the two calls, you end up testing all the permutations.

solveSum(nums, index+1, sumSoFar, target) // skip next number
solveSum(nums, index+1, sumSoFar+nums[index], target); // include next number

Notice as well that this function returns a boolean and that the two recursive calls are joined with an or. This means the statement will be true if any one of the permutations are successful.

makeSum vs. solveSum

You should also notice that there is a helper function for this problem. The way the recursive call works, it needs more than just the numbers list and target. It also needs to track what the current sum is and which index is next to be considered from the vector.

Since the end-user doesn’t need to know how to start the recursive call, this program uses an intermediate step that takes the basic information from the user and creates the first recursive call for solveSum method.

Explore This Example

Take some time to explore this example. This is a good example of the power of recursion. Without the comments, the recursive function is only three lines, yet it creates and tests all possible permutations in those three lines. Try creating your own makeSum calls and see if they pass or not.

Previous6.1.3 Recursion Example: Reverse StringNext6.2 Procedural Recursion

Last updated 3 years ago

Try This Example