Writing Pseudocode for Recursion Quiz Quiz

Explore the fundamentals of writing pseudocode for recursive algorithms with these medium-level questions. Strengthen your understanding of recursive structures, base cases, and flow in algorithmic pseudocode design.

1. Identifying Base Cases

   When writing pseudocode for a recursive factorial function, which base case is typically used for non-negative integers?

   1. If n equals 1 then return n
   2. If n equals 0 then return 1
   3. If n less than 1 then return 0
   4. If n greater than 0 then return n minus 1

   Explanation: The base case for a recursive factorial function is usually 'If n equals 0 then return 1,' as 0! is 1 by definition. Returning 0 for n less than 1 doesn’t produce the correct result for the factorial sequence. Returning n when n is 1 only matches a single value but misses the proper recursive anchoring. Returning n minus 1 for n greater than 0 simply does not specify a stopping condition and may cause infinite recursion.

2. Recursive Call Placement

   In pseudocode, where should the recursive call appear when summing all values in a list from index i to the end?

   1. Immediately before the base case check
   2. After returning the final sum
   3. At the start of the function before any conditionals
   4. Inside the else block after checking if i equals list length

   Explanation: The recursive call happens inside the else block after confirming that the base case hasn't been reached. It should not precede the base case check, as that might cause out-of-bounds errors. Placing it unconditionally at the start ignores necessary termination logic. A recursive call after returning a sum is unreachable, thus incorrect.

3. Pseudocode Return Values

   For a recursive pseudocode function calculating Fibonacci numbers, what should typically be returned in the recursive step for n greater than 1?

   1. Return n minus fibonacci of n minus 1
   2. Return fibonacci of n minus 1 plus fibonacci of n minus 2
   3. Return n times fibonacci of n minus 1
   4. Return fibonacci of n divided by 2

   Explanation: The recursive calculation for Fibonacci numbers is 'fibonacci(n-1) + fibonacci(n-2)', since each term sums the two preceding terms. Multiplying n by fibonacci(n-1) does not match Fibonacci sequence logic. Using division or subtraction does not align with Fibonacci's additive definition. Thus, only the first option provides the correct recursive relationship.

4. Termination Criteria

   Which base case effectively prevents infinite recursion in a pseudocode function that computes the sum of a non-empty array?

   1. If index equals array length minus one then return -1
   2. If array is empty then return 0
   3. If first element is positive then return value
   4. If array length greater than 1 then return array[0]

   Explanation: Returning 0 when the array is empty serves as a reliable base case that stops recursion. Returning the first element when length is greater than one doesn't halt the recursion structure properly. Returning a value based solely on the positivity of the first element ignores the array's structure. Returning -1 when index is at array length minus one is arbitrary and would disrupt proper summing.

5. Recursive Pseudocode Structure

   Which structure best represents the flow of a general recursive function in pseudocode?

   1. Loop through entire input, call function at start
   2. Check base case, return answer if true, else call function recursively
   3. Increment input value and call the function recursively every time
   4. Return only the recursive call without any checks

   Explanation: A well-structured recursive function first checks for a base case before making a recursive call. Simply looping and calling the function does not form a recursive pattern. Neglecting base cases causes infinite loops or stack overflows. Recursively increasing input without conditionals often prevents the function from reaching a valid exit point.