ENGGEN 131 Chap.10 Strings, Files and Recursion

Strings, Files and Recursion

This chapter treats a C string as a character array terminated by a null character and distinguishes visible length from capacity. It builds file loops around successful reads rather than stale end-of-file state, then traces recursion down to a reachable base case and back up through pending returns. The shared theme is proving where processing stops.

What this chapter covers

• 01

  Visible string length and array capacity

• 02

  Null termination and safe construction

• 03

  Successful-read file loops

• 04

  Recursive base cases and progress

• 05

  Call order and return order

Worked example · free

Unwind a recursive sum

Key terms

Null character

The zero-valued character marking the end of a C string.

Base case

A recursive case that returns without making another call.

Call stack

The active function-call frames waiting to complete.

Strings, Files and Recursion FAQ

Exam move

For every C string, record three quantities separately: array capacity, visible character count and space remaining for additional characters plus the null terminator. Six visible characters require at least seven elements. Before copying, concatenating or reading, calculate the largest possible resulting length and verify that the terminator remains within the array.

State whether input should accept a word, a whole line or a fixed field, because whitespace behaviour and width limits must match that requirement. Test string code with empty text, one character, exact-capacity text and input that would exceed capacity. Inspect where the null character is written rather than trusting printed output. A missing terminator can make a later routine continue reading beyond the intended content.

When comparing or transforming text, distinguish visible length from allocated capacity and preserve a stopping character after every mutation. Include leading spaces and embedded whitespace when the contract calls for a line rather than a token. Drive file loops with the success of the read operation.

Check that opening succeeded, attempt a read, and process the record only if the required conversion or line acquisition succeeded. End-of-file is learned through that attempt; testing a flag beforehand can cause the previous buffer to be processed again. Track record count and computation state in a table.

Include an unavailable file, empty file, malformed record and valid final record, then close the stream on normal and failure paths. Trace recursion in two directions. On descent, write one row per call with its argument, whether it is a base case and the operation waiting for a result. At the base case, record the returned value. On ascent, fill each pending result in reverse call order.

Do not add values during descent without identifying which stack frame owns the operation. This method makes the difference between call order and return order visible and prevents the base result from being mistaken for the entire answer. Prove termination with a measure. State a domain for permitted inputs, a base case that returns without recursion and a recursive case that moves the measure strictly toward that base.

Test the base input and the next-smallest input before tracing a larger one. If a call changes n to n plus one while the only base is zero and n starts positive, the measure moves the wrong way. Syntax and initial output cannot compensate for an unreachable stopping condition.

Finish by comparing three stopping boundaries: the null character ends string traversal, a failed read ends record acquisition and the base case ends recursive descent. For each, identify the observable condition, the state that remains valid and the proof that normal processing cannot cross its memory boundary.

Write one iterative and one recursive solution to a small accumulation problem and compare their invariants, storage and termination. Mastery means tracing both control forms accurately and showing that all strings, files and calls stop for a stated reason. For a final synthesis, design a routine that reads bounded text records and recursively counts a chosen character in each accepted string.

State buffer capacity, maximum visible length and null-terminator position before the read. Drive the file loop with successful acquisition and reject malformed or overlong records according to a written policy. For one accepted string, draw every recursive call, its argument position, base case and pending addition, then unwind the returned counts. Test empty text, exact-capacity text, an empty file and a final valid record.

The combined trace should prove three independent stopping boundaries: terminator, failed read and reachable base case. It also exposes any repeated stale buffer, missing terminator or recursive step that moves away from completion.