Recursion: Functions That Call Themselves | Programming in C

UPI Study › Courses › Programming in C › Free lessons › Lesson 6.6 Free with a free account

Recursion: Functions That Call Themselves

Programming in C · Chapter 6: Functions, Scope, Storage Classes, and RecursionSection 6.6 · lesson 38 of 786 min · free with a free account

← Pass by Value vs. Pass by Reference in CNext lesson: Workshop: Multi-Function Programs and Recursion →

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

In this lesson

Writing C functions that solve a problem by calling themselves.

  • Identify the base case and recursive case of a recursive function
  • Trace recursive calls and returns on the call stack
  • Write recursive factorial and digit-sum functions
  • Compare recursion with an equivalent loop

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 (855 words). Read along, or search it.

Opening Analogy

A Hall of Mirrors

Stand between two mirrors, and you see a hall of smaller and smaller copies of yourself, each one inside the last. A function can do something like that. It can call itself, to solve a smaller piece of the same job. It sounds like a trick that never ends. And it would never end, except for one small rule you'll learn here.

Two Required Parts

Base Case and Recursive Case

A function that calls itself is called recursive. Every recursive function needs exactly two parts. The base case: a situation so small that the answer is simple, so the function stops calling itself. And the recursive case: a call to itself with a smaller problem, one step closer to the base case. Think of a rocket countdown. If the count is 0, say Liftoff, and stop. Otherwise, say the number, then count down from one less. Run it with 3. Three, two, one, Liftoff! A countdown that uses a smaller countdown.

Worked Example

Factorial Through Stacked Calls

The factorial of a number multiplies every whole number from 1 up to it. 4 factorial is 4 times 3 times 2 times 1, which is 24. Notice that 4 factorial is just 4 times 3 factorial. Each factorial hides a smaller one inside it. The base case is 1 factorial, which is 1. So fact returns 1 when n is at most 1. Otherwise, it returns n times fact of one less than n. Two printf lines show the work. Run it. The calls start, each stepping into the next: four, three, two, one. Every call gets its own frame on the call stack, holding its own n. The pile grows until the base case. Then fact of 1 returns first, and the answers flow back down: 1, then 2, then 6, then 24. The last call to start is the first to finish. And nothing was multiplied until the base case answered. What about fact of 0? Mathematicians define 0 factorial as 1, and the test n at most 1 catches 0 too.

Worked Example

Summing a Number's Digits

Recursion isn't only for multiplying. Take the sum of a number's digits: 4821 gives 4 plus 8 plus 2 plus 1, which is 15. Two tricks from lesson 2.5 do the work. n percent 10 is the last digit, and n divided by 10 chops that digit off. The base case is a one-digit number, which is its own digit sum. So the answer is the last digit, plus the digit sum of the rest. Run it: 15. Each call hands the next a number one digit shorter, and the sums add up on the way back.

Common Mistake

Runaway Recursion and Stack Overflow

Now forget the base case. This countdown never stops calling itself. Every call adds a frame to the stack, and the stack has a fixed size. It runs out of room: a stack overflow, and the operating system stops the program. Clang catches this obvious case. Build it, and it warns: all paths through this function will call itself. But it can't catch every runaway. Add a base case, and make the call move away from it, with n plus one. The build is silent. Starting at 3, the count never reaches 0. So ask before every run: does each call get closer to the base case?

Comparison

Recursion Versus a Loop

Any recursive function can also be written with a loop. Here's factorial both ways: recursion on the left, a for loop on the right. Run both with 5. Each prints 120. A loop uses one frame, and reuses its variables, so it's lighter. A recursive function makes a frame for every call, which costs memory and time. A loop fails by never reaching a false condition, and keeps running. Recursion fails by never reaching its base case, and overflows the stack. Recursion wins when a problem is naturally made of smaller copies of itself, and the code gets shorter and clearer.

Quick Check

Printing After the Recursive Call

Quick check. This function looks like the countdown, but two of its lines have traded places. Main calls show of 3. What does it print? Pause and predict. Build and run: one, two, three. Show of 3 calls show of 2 before it prints anything, and show of 2 calls show of 1. Show of 0 returns at once. Then each waiting frame finishes its printf on the way back: 1, then 2, then 3. Work done after the recursive call happens in reverse order, just like the returns of fact.

Quick Check

The Digit Sum of 305

One more, back to digit sum. This time main asks for the digit sum of 305. What does it return? Pause and predict. Build and run: eight. 305 gives 5, plus the digit sum of 30. 30 gives 0, plus the digit sum of 3. And 3 is a base case. So it's 5 plus 0 plus 3: eight. The zero in the middle still costs one call.

Key Takeaways

Recursion in Review

To sum up. A base case stops the calls, and the recursive case makes the problem smaller. Each call gets its own frame on the stack, with its own variables. The last call to start is the first to return, so answers come back in reverse order. And with no base case reached, the stack overflows. A loop is often the lighter choice.

About Programming in C at UPI Study

Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. 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: C vs C++

Why take it here

Why students take Programming in C with UPI Study

How programs work close to the machineProgramming in C teaches how a program uses memory: variables and data types, control flow, functions, arrays and strings, pointers, files, structures and dynamic memory. C is the base for operating systems, embedded devices and many computer-science courses.
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

Programming in C 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 Recursion: Functions That Call Themselves

What are the base case and recursive case in recursion?
The base case is a problem small enough to answer directly, so the function stops calling itself. The recursive case calls the same function on a smaller problem, one step closer to the base case. In a countdown, a count of 0 prints Liftoff and stops; otherwise the function prints the number and then counts down from one less.
How does a recursive factorial function work in C?
It uses the fact that n! equals n times (n - 1)!. The function returns 1 when n <= 1, which also covers 0! = 1, and otherwise returns n * fact(n - 1). For fact(4), calls pile up for 4, 3, 2 and 1, then the answers come back in reverse: 1, 2, 6 and 24. No multiplication happens until the base case answers.
What causes a stack overflow in a recursive function?
A stack overflow happens when recursion goes deeper than the call stack can hold, most often because it never reaches its base case. Each call adds a frame to the fixed-size stack, and when it runs out of room the operating system stops the program. Clang warns when every path calls the function again, but it cannot catch a call that moves away from the base case, such as n + 1 when counting down to 0.
Is recursion or a loop better in C?
Both can solve the same problems, but a loop is usually lighter, because it uses one frame and reuses its variables, while recursion makes a new frame for every call. Recursion is the better fit when a problem is naturally made of smaller copies of itself and the recursive code is shorter and clearer. Computing 5! either way gives 120.

About the Programming in C course

How many college credits is Programming in C?
Programming in C (Computer Science 240) 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 Programming in C cost and what is included?
$250, paid once, with lifetime access: all 78 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 Programming in C take?
It is self-paced with no deadlines. The 78 lessons total about 9 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 Programming in C.

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

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