Nested Iteration, Explained with Code Examples

UPI Study › Courses › C++ Programming › Free lessons › Lesson 5.5 Free with a free account

Nested Iteration

C++ Programming · Chapter 5: IterationSection 5.5 · lesson 33 of 84video coming soon

← The do-while LoopNext lesson: break, continue, and Other Flow Controls →

Earn 3 college credits for C++ ProgrammingRecommended for credit by NCCRS · Computer Science 242 · self-paced · one payment, lifetime access
Enroll in C++ Programming · $250 →Download the syllabus (PDF)

In this lesson

Placing loops inside loops for multi-layered problems.

  • Count exactly how often an inner body runs
  • Explain why the inner counter restarts
  • Print rectangles and triangles, with the break in place
  • Lay out tables as rows and cells

Transcript

Everything said in the video, section by section (1,252 words). Read along, or search it.

Opening Idea

When Loops Multiply Instead of Add

A loop repeats a body. When that body is itself a loop, one pass of the outer repetition contains an entire run of the inner one. And the work no longer adds up. It multiplies. This is the shape behind every grid, table, calendar, and printed pattern. And it's the first construct where a small change to a bound can have a very large effect.

Core Rule

Inner Loop Finishes Before Outer Advances

There's a single rule, and everything else follows from it. For each pass of the outer loop, the inner loop runs all the way through, from its start to its finish. The outer loop doesn't advance until the inner one has completely finished. Here, i is 1, and j runs 1, then 2. Then i becomes 2, and j starts over: 1, then 2. Then i is 3, and j runs 1, 2 once more. The first number changes slowly, and the second changes quickly. That's always the signature of nesting, like the hands of a clock. The restart is the part that surprises people. The inner loop's initialization is part of the inner loop, so it runs again every time the inner loop is entered.

Counting Passes

Bounds Multiply into Large Totals

With independent bounds, the number of times the innermost body runs is simply the product. Four outer passes of six inner passes is 24. Twelve months of up to 31 days is 372. A thousand by a thousand is a million, from two innocent-looking bounds. The last loop counts something else, and we'll come to it. Nothing about the code looks a thousand times bigger. Doubling one bound doubles the total. But doubling both quadruples it, so the cost of a nested loop grows far faster than the numbers in it suggest.

Quick Check

Doubling Both Bounds of Five by Eight

Pause and predict. An outer loop makes 5 passes, and an inner loop makes 8. Now double both bounds. How many times does the inner body run? One hundred sixty: ten times sixteen. That's four times the original forty, because doubling both bounds quadruples the work.

Optimization

Lifting Outer-Only Work Out of the Inner Loop

The second consequence: anything placed in the innermost body pays that multiplied price. Suppose a value called base depends only on i. Computed inside the inner loop, it runs a million times, and 999,000 of those calculations are wasted. Lifted into the outer body, it runs a thousand times. Moving one line up a level removes all the waste, and the results are identical.

Grid Pattern

Rows Outside, Columns Inside

The most direct use of nesting is anything laid out as a grid. The mapping is always the same. The outer loop counts rows, and the inner loop counts positions within one row. Here, four rows, and in each row, six columns, printing a star at each position. After the inner loop finishes, still inside the outer body, the program prints a line break. The result: four rows of six stars.

Common Mistake

Line Break Inside the Inner Loop

The line break is the part to get right, and its position isn't a matter of taste. Here is a smaller grid, 2 rows of 3, so the results fit on screen. Put the break inside the inner loop, and a break follows every star: one tall column.

Common Mistake

Line Break After the Outer Loop

Put it after the outer loop, and you get one long line of 6 stars. Every star is printed before the only break arrives.

Correct Placement

One Break per Completed Row

After the inner loop, inside the outer body, gives the intended grid: one break per completed row, which is one per outer pass. It belongs there because that's exactly the moment one row has been completed, and the next hasn't yet begun.

Dependent Bounds

Inner Bound Tied to the Outer Variable

Nothing requires the inner bound to be a fixed number. It can be an expression involving the outer variable. The moment it is, each outer pass runs a different number of inner passes. Change the inner condition to column at most row, and each row is one longer than the last. That's a triangle. 1 plus 2 plus 3 plus 4 plus 5: 15 inner passes, against 25 for a square. Swap one fixed bound for the outer variable, and both the shape and the work change.

Cost Analysis

Triangular Totals Still Grow Quadratically

The total for a triangular loop is 1 plus 2, and so on up to n. That comes to n times n plus 1, over 2. It's a little over half of n squared. For 5 rows, 15 rather than 25. For 1,000 rows, 500,500 rather than a million. The saving is real, but it isn't a change of scale. A triangular loop still grows in proportion to the square of its bound.

Variation

Flipping the Triangle Upside Down

Start the inner loop from the outer variable, instead of ending it there, and the triangle turns upside down: five stars, then four, down to one.

Worked Example

Multiplication Table with Aligned Columns

A table is a grid with values in it rather than characters, and it's written with exactly the same shape. The outer loop decides what a row is. The inner loop decides what a single cell is. Here, each cell prints row times column. Only one expression changed from the star pattern. And s t d set w reserves a fixed width for each value, so the columns line up, however many digits a number has. The structure didn't change at all. Once you can see a problem as rows of cells, the loop writes itself.

Choosing Levels

Deciding Which Variable Goes Outside

The same skeleton produces a report. Saying one sentence out loud before writing the code settles which variable belongs where. A star rectangle: rows outside, positions inside. A multiplication table: the first factor outside, the second inside. A quarterly report: departments outside, one per line, and quarters inside. And a calendar year: months outside, days inside.

Good Habits

Keeping Nested Loops Manageable

A few habits keep nesting manageable. Use different variables at each level. Reuse one for both loops, and the inner loop destroys the outer loop's position. Here, the inner loop reuses i. It counts three cells and leaves i at 3, so the outer update makes it 4 and the test fails. Three cells, not nine. Choose names that say what the level is: row and column, or month and day. Never change the outer counter from inside. And keep one indentation level per depth. And stop at two levels where you can. A third level is usually a signal that part of the work should be described separately.

Self Check

What Does One Outer Pass Accomplish?

When you've written a nested loop, answer one question out loud. What does a single pass of the outer loop accomplish? It prints one complete row. It produces one department's line of figures. If the answer comes easily, the structure is right. If you find yourself describing single cells, the levels have been mixed up. Something that belongs to a whole row is running once per cell.

Key Terms

Vocabulary of Nested Loops

A few key terms. A nested loop is a loop written inside the body of another loop. The inner loop restarts from its initialization on every outer pass. Independent bounds don't involve the outer variable: a rectangle, and a product. Dependent bounds do: a triangle, and a smaller total. And the innermost body is the deepest level, the statements that run the multiplied number of times.

Key Takeaways

Summary and a Five Hundred Challenge

To summarize. The inner loop runs completely for every pass of the outer loop, and its counter restarts each time. Totals multiply, so lift anything that depends only on the outer variable out of the inner body. The line break goes after the inner loop, inside the outer body. Dependent bounds give triangles. Check your structure by saying what one outer pass accomplishes. Here's something to think about. With bounds of 500 and 500, an expression depends only on the outer variable. How many calculations does lifting it out of the inner body save?

About C++ Programming at UPI Study

C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take C++ Programming with UPI Study

Your first real programming languageC++ teaches how programs really work: variables, control flow, functions, memory and objects. It is the base for data structures, algorithms, systems and game programming, and for most computer-science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Nested Iteration

How do you count how many times the inner body of a nested loop runs?
With independent bounds, multiply the outer pass count by the inner pass count. Four outer passes of six inner passes run the body 24 times. Doubling both bounds quadruples the total: 5 by 8 is 40 runs, but 10 by 16 is 160. If the inner bound depends on the outer variable, add up the inner counts instead. A 5-row triangle gives 1+2+3+4+5 = 15.
Why does the inner loop counter start over on every pass of the outer loop?
The inner loop's initialization is part of the inner loop, so it runs again every time the inner loop is entered. For each outer pass, the inner loop runs completely from start to finish. If i is 1, j runs 1, 2. When i becomes 2, j runs 1, 2 again. The outer variable changes slowly while the inner one changes quickly.
How do you print a rectangle or triangle with nested loops, and where does the line break go?
Use the outer loop for rows and the inner loop for positions in a row, with one line break after the inner loop but inside the outer body. For a triangle, tie the inner bound to the row: for (int row = 1; row <= 3; row++) { for (int col = 1; col <= row; col++) cout << '*'; cout << '\n'; } prints 1, 2, then 3 stars per line. A break inside the inner loop makes one tall column. A break after the outer loop makes one long line.
How do you print a multiplication table with aligned columns in C++?
Treat the table as rows of cells: the outer loop picks the row, the inner loop picks the cell, and each cell prints row times column with setw for a fixed width. For example, for (int r = 1; r <= 3; r++) { for (int c = 1; c <= 3; c++) cout << setw(4) << r * c; cout << '\n'; } needs the iomanip header. Columns line up as long as each number fits the width.

About the C++ Programming course

How many college credits is C++ Programming?
C++ Programming (Computer Science 242) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does C++ Programming cost and what is included?
$250, paid once, with lifetime access: all 84 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does C++ Programming take?
It is self-paced with no deadlines. The 84 lessons total about 0 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in C++ Programming.

84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in C++ Programming →Download the syllabusEvery course with PRO →
C++ Programming
3 credits · NCCRSEnroll →