Week 8 · Foundation

Recursion and files

This lesson has two powerful topics. The first is recursion: a function calling itself. At first it feels strange, but it simplifies some problems surprisingly well. The second is files: storing data on disk so it remains even after the program ends. We will watch recursion in a live call stack diagram.

What you will learn in this lesson

Understand what recursion is and why the base case matters

See how a recursive function solves a problem by shrinking it

Watch how the call stack works

Compare recursion and a loop

Open and close a file with fopen and fclose

Write to a file (fprintf) and read from a file (fgets)

8.1 What is recursion?

Recursion means a function calling itself. The first time you hear it, this sounds strange: how does a function call itself? But the idea is simple: we turn a big problem into a slightly smaller, but otherwise identical, problem.

Imagine two mirrors facing each other. In each mirror there is another mirror, and inside that yet another mirror, and so on. Recursion is the same: inside every call there is another, smaller copy of itself.

For example, counting down a number. sanash(3) first prints 3, then calls sanash(2), which prints 2 and calls sanash(1), and so on. Each call is a little smaller.

Recursion has two parts: the base case (when to stop) and the recursive step (moving to a smaller problem). We will look at both together.

8.2 Base case

If a function always keeps calling itself, it never stops and the program crashes. That is why every recursion must have a base case: the condition that stops the recursion. In the countdown below, the base case is n == 0: when it reaches here the function does not call itself, it simply returns.

sanash.c

1void sanash(int n) {

2 if (n == 0) return; // base case

3 printf("%d\n", n);

4 sanash(n - 1); // recursive step

Click the Run button and see how sanash(3) works:

Countdown Run

terminal

Click the «Run» button: 3, 2, 1 are printed, then it stops when it reaches n == 0.

8.3 Recursive step

In the recursive step the problem gets smaller each time and gets closer to the base case. The classic example is the factorial. n! is the product of the numbers from 1 to n. Its recursive definition is very elegant: n! = n * (n-1)!, and the base case is 1! = 1.

factorial.c

1int factorial(int n) {

2 if (n == 1) return 1; // base case

3 return n * factorial(n - 1);

Choose a number and see how the factorial expands:

Factorial expansion choose a number

n =

terminal

8.4 Call stack

Now the most important part: what happens inside recursion? Every function call adds a new frame to the call stack in memory. This is exactly the same stack (LIFO) from last week! The calls pile up, and when the base case is reached they return one by one, with the answers multiplied along the way.

Use Next step to follow factorial(4). The green frame is the call that is returning right now:

Call stack tracer step through it

top of the stack (last call)

Notice: the calls first pile down (4, 3, 2, 1), then starting from the base case they return up (1, 2, 6, 24). This is exactly why recursion is built on the stack.

8.5 Recursion vs loop

The factorial could also be written with a loop. Many problems can be solved both ways. The choice depends on clarity and the nature of the problem:

Property	Recursion	Loop
Code look	sometimes simpler, more natural	sometimes longer
Memory	stack frames (more)	compact
Very deep	the stack can overflow	no problem
Suitable problem	tree, folder, divisible	simple repetition

In short: a loop is good for simple repetition. But if the problem divides itself into small copies (walking a tree, folders inside folders), recursion is much more natural and easier to read.

8.6 Example: Fibonacci

The Fibonacci sequence is a famous example of recursion. Each number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2). The base cases are: fib(0) = 0 and fib(1) = 1. The sequence: 0, 1, 1, 2, 3, 5, 8, 13, ...

Choose a number and see the result along with the sequence:

Fibonacci choose a number

fib(

) = 13

Note: the simple recursive Fibonacci is slow, because it recomputes the same value again and again (inside fib(5), fib(3) is called several times). This can be sped up later with memoization.

8.7 Files: opening and closing

Now the second topic. Until now, once the program ended, all data was lost. A file stores data on disk, so it stays in place even when the program runs again. To work with a file in C, we first open it, use it, then close it.

fayl.c

1FILE *f = fopen("matn.txt", "w"); // open

2// ... work with the file ...

3fclose(f); // close, required!

fopen opens the file and returns a pointer to it (FILE *). The second parameter is the mode: it tells what the file is being opened for:

"r" read: for reading from an existing file
"w" write: writes anew, the old content is erased
"a" append: writes added to the end

After you finish using a file, calling fclose is required, just like free after malloc. Otherwise the written data may not be fully saved to disk.

8.8 Writing to a file

To write text to a file we use fprintf. It is exactly like printf, except it takes a file pointer as its first parameter: fprintf(f, "%s\n", matn). Enter a line below and write it to the file:

Writing to a file (fprintf) add a line

matn.txt

8.9 Reading from a file

To read from a file, fgets reads one line, or fscanf reads formatted data. Usually we read the file from start to end, line by line, until the file ends. The file is ready below. Read it one by one with Read next line:

Reading from a file (fgets) line by line

royxat.txt

terminal

Make a prediction

What does factorial(3) return?

8.10 Going deeper advanced

A few more important aspects of recursion and files.

Stack overflow

If the recursion is too deep (or the base case is wrong and it never stops), the call stack fills up. This is called a stack overflow and it crashes the program. That is why the base case must be correct and always reachable.

Text and binary files

Files come in two kinds. Text files (txt) consist of human-readable letters. Binary files (image, video, database) consist directly of bytes and are read through a special program. Both are opened with fopen; only the mode and the way of reading differ.

There is a place where recursion and files connect: recursion fits very well for going through folders inside folders. Each folder can contain more folders, which is exactly a recursive structure.

Glossary of terms

recursiona function calling itself.

base casethe condition that stops the recursion.

call stackthe stack where function calls are stored.

fopen / fcloseopening and closing a file.

fprintfwrites formatted text to a file.

fgetsreads one line from a file.

8.11 Knowledge quiz

16 questions. To complete the week, answer at least 11 of them correctly.

Congratulations! Week 8 is complete

Now you understand recursion and working with files: the base case, the call stack, as well as opening, writing to and reading from a file. Only one week is left, you have almost made it!

Next week: Debugging and the final project (types of errors, finding them and building a project). This is the last week of the Foundation course!

Go to the final module