Recursive contracts, base cases and progress

≈ 45 min

Recursive contracts, base cases and progress

Recursion solves a problem by calling the same method on a smaller version of that problem. It is trustworthy only when the contract states what the method returns for any allowed input, the base case handles the smallest input directly, and every recursive call moves closer to that base case. The call stack remembers unfinished work while smaller calls run.

For factorial, factorial(0) is 1; factorial(n) is n times factorial(n - 1) for positive n. The base case prevents endless calls, and n - 1 is a measurable move toward zero. A method that calls itself with the same argument has not made progress, even if the formula looks elegant.

Worked reasoning. To total marks in an array from index i, return 0 when i reaches the array length. Otherwise return marks[i] plus totalFrom(i + 1). Each call has one job: add the current mark and delegate the remaining suffix. Trace the calls down to the empty suffix, then trace return values back up.

Exam lens. When tracing recursion, write each call, identify the first base case reached, then resolve returns in reverse order. Do not confuse the order of calls with the order of returned answers.

java

Uses Uvero's optional secure Java practice service. If it is unavailable, your lessons and progress still work.

Which statement is the most defensible principle for Recursive contracts, base cases and progress?

A recursive method needs a precise smaller subproblem, a terminating base case and visible progress toward that case.

Treat an implementation detail as more important than the stated rule.

Assume one successful run proves the system is correct in every case.

Avoid recording assumptions, limits or failure conditions.

Enter the key term for Recursive contracts, base cases and progress. What condition stops a recursive method from calling itself again?

A recursive search calls search(items, index) again with the same index whenever the item is not found. What must change?

The recursive call must move to a smaller remaining problem, for example by increasing the index or shrinking the interval.

Use a larger class or broader permission without stating a rule.

Trust the first output and skip a boundary or failure check.

Hide the decision so affected people cannot inspect it.

Name the concise safeguard or principle that completes this lesson’s scenario: A recursive search calls search(items, index) again with the same index whenever the item is not found. What must change?