When to Call Itself vs. When a Loop Does Better

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 8.1 Free with a free account

When to Call Itself vs. When a Loop Does Better

Data Structures and Algorithms · Chapter 8: RecursionSection 8.1 · lesson 31 of 878 min · free with a free account

← Proving That an Algorithm Works CorrectlyNext lesson: Thinking Recursively →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Choosing between recursion and loops by structure, stack use, and repeated work.

  • Compare recursive and iterative solutions to the same problem
  • Explain why very deep recursion causes a StackOverflowError in Java
  • Convert tail-recursive and general recursive methods into loops
  • Decide when recursion or a loop fits a problem better

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

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

Opening Question

Folder Sizes Versus Running Totals

How much storage does a folder use? It holds files, and other folders, which hold more files and folders. A natural answer: the files here, plus the size of each folder inside. That answer repeats the question on smaller pieces. Now add up one to a hundred: you'd just keep a running total. Both repeat work, but they feel different. Java has a tool for each: a loop, and a method that calls itself. Neither is better everywhere.

Worked Example

Summing One to n Both Ways

Take one small problem both ways: the sum from one to n. Repeating with a loop is called iteration. Sum loop keeps a total and a counter, and adds the counter each pass. The recursive version rests on one fact: the sum to n is n, plus the sum to n minus one. So it calls itself with a smaller number. It needs a place to stop, or it would call itself forever. When n reaches zero, it returns zero directly. Run both on four: ten, and ten. A third copy prints each call as it starts and finishes. Four calls start before any of them finishes. Only when the innermost returns zero can the others finish, from the inside out.

Decision Criteria

Four Things to Weigh

For this problem, the loop is the simpler choice. To decide in general, look at four things. Structure: is the problem made of smaller copies of itself? Readability: which version reads like the description? Stack usage: how much memory does it need as the input grows? And repeated work: does it solve the same smaller problem many times?

Worked Example

Folder Sizes with a Record

Back to folders. A folder is a size of its own, plus a list of folders inside it, each with exactly the same shape. That's a recursive structure. A record is Java's compact way to declare a small data holder. Total size rec reads like the definition: its own size, plus the total of each child. A folder with no children has an empty list, so the loop does nothing. That's the stopping case, built into the data. A loop can't go down into a folder and come back. So total size loop keeps a to-do list of waiting folders, called pending. Last in, first out: a stack. The test root holds docs, pics, and a file. Both give eighty-eight. But only the recursive one reads like the definition.

Memory

Frames and the Fixed-Size Call Stack

Each call gets a block of memory called a frame, for its parameters and local variables. Frames live on the call stack, and a frame goes only when its call returns. A loop reuses the same variables, so it needs the same memory for four as for a million. Recursion needs one frame for every call still waiting. The call stack has a fixed size. This method does nothing but call itself. Run it: after tens of thousands of calls, Java runs out of room and stops it. The exact count depends on the machine and the settings. It even changes from run to run, so a program should never depend on it.

Repeated Work

Fibonacci Recomputes the Same Values

Repeated work. Fibonacci numbers start zero, one, one, two, three, five, each the sum of the two before. That definition becomes a method that calls itself twice. A loop version just carries the last two values forward. The calls counter only counts how often the recursive method is entered. For fib of five, the recursive method works out fib of three twice, and fib of two three times, each from scratch: fifteen calls. And it snowballs. For thirty, the loop makes twenty-nine passes. The recursive version makes over two and a half million calls.

Quick Check

Counting Calls for Fib of Six

Quick check. The same method now computes fib of six, and counts its calls. How many calls does it make? Pause, and predict. Twenty-five. The first call makes one call for fib of five, which takes fifteen, and one for fib of four, which takes nine. One plus fifteen plus nine. Sixteen forgets the whole fib of four branch. When a method calls itself more than once, ask whether the calls overlap.

Tail Calls

Accumulators and Tail Recursion

In sum rec, the self-call still has work left after it returns: it must add n. That pending addition is why the frame waits. A call is a tail call when it's the very last thing the method does. To make the sum tail-recursive, carry the running total along as an extra parameter, an accumulator. Now the addition happens before the call, and the call just returns what it gets back. Some languages notice a waiting frame with nothing left to do, and reuse it.

Quick Check

Tail Recursion on a Million

Quick check. The program you just saw calls sum tail with a million, inside a try block. In Java, what does that call do? Pause, and predict. It overflows, just like sum rec. Java doesn't reuse frames for tail calls: neither the language nor its usual runtime does tail-call optimization. So a million nested calls still need a million frames. Tail form gives no protection in Java.

Common Mistake

Catching Overflow Is Not a Fix

Run it. Sum tail of a hundred works. But on a million, sum rec and sum tail both overflow. Only the plain loop handles a million. And don't catch this error as a fix. The program here catches it only to display it. Change the method instead: keep the depth small, or use a loop.

Conversion

Turning Tail Recursion into a Loop

A tail-recursive method converts to a loop mechanically. The parameters become local variables, starting with the first call's values. The stopping case becomes the condition that ends the loop. And the self-call becomes new values assigned to those variables, before the loop repeats. That turns sum tail into sum tail as loop, which handles a million without trouble.

Conversion

Explicit Stacks Replace Waiting Frames

Other recursion, like sum rec or the folders, needs the waiting frames replaced by something you control: an explicit stack, like pending. Put the starting problem on the stack. While it isn't empty, take one off, do its work, and push the smaller problems it creates. It lives in ordinary memory, and grows far larger. The reverse works too. The changing variables become parameters, and the loop condition becomes the stopping case. But in Java, do that only when the result reads better, and the depth stays small.

Decision Guide

Recursion or a Loop

Put it together as a short guide. Is the problem nested, like folders or trees, with small depth? Recursion fits. Is it a plain sequence, like adding one to n, or two million records? Use a loop: recursion would need a frame for each. Does a recursive version solve the same subproblems again, like Fibonacci? Use a loop. And if the depth is unknown, and could be huge, use a loop with an explicit stack.

Key Takeaways

Recursion Versus Iteration Essentials

To sum up. A loop repeats by updating variables. A recursive method repeats by calling itself on a smaller problem. Recursion fits nested problems, and a loop fits plain sequences. Every waiting call uses a frame, so very deep recursion overflows. Java doesn't optimize tail calls. And a method that calls itself twice may repeat huge amounts of work.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. 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 All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software 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

Data Structures and Algorithms 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 When to Call Itself vs. When a Loop Does Better

When should you use recursion instead of a loop in Java?
Use recursion when the problem is nested, made of smaller copies of itself like folders or trees, and the depth stays small, because the recursive code then reads like the definition. Use a loop for plain sequences such as summing the numbers from 1 to n, for very deep inputs, or when a recursive version solves the same subproblems again. If the depth is unknown and could be huge, use a loop with an explicit stack.
Does Java optimize tail recursion?
No, Java does not perform tail-call optimization: neither the language nor its usual runtime reuses a frame for a tail call. A tail-recursive sum that carries an accumulator, such as return sumTail(n - 1, acc + n);, still needs one frame per call, so calling it with n = 1,000,000 overflows the stack just like the plain recursive version. Rewriting it as a loop removes the problem.
How do you convert a recursive method into a loop?
For a tail-recursive method, the parameters become local variables starting with the first call's values, the base case becomes the condition that ends the loop, and the self-call becomes new values assigned to those variables. For other recursion, replace the waiting frames with an explicit stack: push the starting problem, then repeatedly pop one, do its work, and push the smaller problems it creates until the stack is empty.
What causes a StackOverflowError in recursion?
A StackOverflowError happens when too many calls are waiting at once, because each call gets a frame on the call stack and the stack has a fixed size. A loop reuses the same variables, but recursion needs one frame for every unfinished call. After tens of thousands of nested calls, Java typically runs out of room; the exact limit depends on the machine and settings, so code should never rely on it.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) 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 Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 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 Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 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 Data Structures and Algorithms.

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

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →