Workshop: Multi-Function Programs and Recursion, Explained

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

Workshop: Multi-Function Programs and Recursion

Programming in C · Chapter 6: Functions, Scope, Storage Classes, and RecursionSection 6.7 · lesson 39 of 787 min · free with a free account

← Recursion: Functions That Call ThemselvesNext lesson: One-Dimensional Arrays in C →

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

Splitting programs into one-job functions and tracing recursive calls.

  • Split a program into small functions that each do one job
  • Use an early return to stop on invalid input
  • Count recursive calls with a file-level counter
  • Debug a recursive function with a trace of each call

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

Workshop Plan

Building in Small Tested Pieces

A big program is never written in one go. Builders cut the job into small pieces, make sure each piece works, and only then join them. In this workshop, you'll build three programs for the Starlight Arcade that way. An arcade score tool split into functions, a recursive power and Fibonacci counter, and a palindrome check that explains itself.

Planning

Read, Check, Compute and Print

Program one turns a game score into prize tickets: one for every 100 points, plus 5 bonus tickets at 900 or more. Scores run from 0 to 1000. Priya splits the job into four small functions, each with one task: read, check, compute, and print. A function called play_round joins them, in that order. A function that does one thing is easy to test on its own. So build in that order too. Write read_score, and test it. Then add is_valid, and test a good number and a bad one. Then the rest.

Worked Example

A Score-to-Ticket Program

Here's the finished program. read_score prints a prompt, reads a number with scanf, and returns it. is_valid returns 1 when the score is from 0 to 1000, and 0 otherwise. The whole answer is one logical expression. tickets_for divides by 100, and adds the bonus at 900 or more. print_report only prints, so its return type is void. play_round reads a score and checks it. If the score is bad, it prints a message, and leaves early with a plain return. Build it, and run it with two players, who type 1250, then 930. Player one's score is above 1000, so is_valid returned 0, and play_round left early. Player two scored 930: 9 tickets, plus 5 bonus, makes 14.

Quick Check

Tickets for a Top Score

Quick check. Here are the checker and the ticket counter on their own, testing the top score, 1000. How many tickets does it print? Pause and predict. Build and run: 15 tickets. 1000 is valid, because the test is less than or equal to 1000. Then 1000 over 100 is 10, and a score of at least 900 adds 5. Testing the edge values is exactly why each piece stands alone.

Worked Example

Counting Power and Fibonacci Calls

Program two: two classic recursive jobs, and a counter to show what each one costs. Power of 2 and 10 means 2 times itself, 10 times. That's 2 times power of 2 and 9. The base case: anything to the 0 is 1. A Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8. So fib of n adds fib of one less, and fib of two less. A file-level variable, calls, goes up by one every time either function starts. That's file scope, from lesson 6.3. Run it. The power took 11 calls: one for each exponent from 10 down to 0. fib of 4 took 9 calls, and fib of 10 took 177. And fib of 20 needed 21891 calls, though its answer is only 6765. Each fib call makes two more calls, and they repeat each other's work. A loop would need only about 20 steps for the same answer.

Call Tree

Where Nine Fibonacci Calls Go

Here's where fib of 4's nine calls go. fib of 4 calls fib of 3 and fib of 2, and each of those calls two more, down to the base cases. fib of 2 is worked out twice, fib of 1 three times, and fib of 0 twice. Nine calls, for an answer of 3.

Worked Example

A Recursive Palindrome Check

Program three. A palindrome number reads the same forward and backward, like 1221. To test one, reverse its digits, and compare. Reversing is recursive. Peel the last digit off n, and tack it onto the end of a growing rev, with rev times 10 plus n percent 10. Then continue with n over 10. The base case is n equal to 0: no digits left, so rev is the answer. A trace line prints what the function receives on every call, and the variable debug switches it on or off. Build it, and type 1221. n shrinks while rev grows: 1, 12, 122, and finally 1221, the same as the input. Yes. For 1234, the trace ends at 4321, so the answer is no. When you're done, set debug to 0, so players never see the trace.

Debugging

A Trace Finds the Missing Times Ten

Sam's first checker said 1221 was not a palindrome. Here's his recursive line: rev plus n percent 10, with no times 10. Run it, and read the trace with Priya. The second call looks fine: rev is 1. But the third call shows rev 3, where the right code had 12. The digit was added on, not shifted left. That's the first call where the numbers go wrong. Put the times 10 back, and run again: it reads the same both ways. When a recursive function gives a wrong answer, a trace like this shows you the first call that stops matching your work on paper.

Quick Check

Reversing 560

Quick check. Here's the fixed reverse, with a shorter trace line. This time main tests 560. On the last trace line, what is rev? Pause and predict. Build and run. The last line shows rev 65, so 560 is not a palindrome. The trailing 0 was peeled off first, and 0 times 10 plus 0 is still 0. A whole number can't keep a leading zero, so rev ends at 65.

Challenges

Two Ideas to Try

Two ideas to try on your own. Make a score of 500 or more earn 2 extra tickets, by changing only tickets_for. And write a recursive count_digits. Its base case is a number below 10. Work out each answer by hand first, then run.

Key Takeaways

Multi-Function Programs in Review

To sum up. Give each function one job, and test each piece before you join them. Check input first, and leave early with return when it's bad. A file-level counter shows what a recursive function really costs. And a trace of each call's values points straight at the first wrong step.

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 Workshop: Multi-Function Programs and Recursion

Why should each C function do only one job?
A function with one job is easy to test on its own before it joins the rest of the program. A score tool can be split into read_score, is_valid, tickets_for and print_report, joined by play_round. Testing is_valid and tickets_for at the edge value 1000 confirms it is valid and earns 10 tickets plus a 5-ticket bonus, 15 in all, before the pieces are combined.
Why is recursive Fibonacci so slow?
Each fib call makes two more calls, and those calls repeat each other's work. fib(4) makes 9 calls, computing fib(2) twice, fib(1) three times and fib(0) twice. fib(10) makes 177 calls, and fib(20) makes 21,891 calls for an answer of only 6,765. A loop needs only about 20 steps for the same result.
How do you check if a number is a palindrome with recursion in C?
Reverse the digits recursively and compare the result with the original. Each call peels off the last digit with n % 10, adds it to rev * 10, and continues with n / 10; when n is 0, rev is the answer. For 1221, rev grows 1, 12, 122, 1221, matching the input. For 1234 it ends at 4321, so 1234 is not a palindrome.
How do you debug a recursive function that gives a wrong answer?
Add a trace line that prints the values each call receives, then compare them with your work on paper to find the first call that stops matching. A reverse function missing its times 10 showed rev as 3 on the third call for 1221, where correct code has 12, because the digit was added instead of shifted left. A debug variable can switch the trace off afterward.

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 →