Question

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

• A.

  E1: head == NULL
  E2: 1 + getListSize(head)

• B.

  E1: head->next == NULL
  E2: 1 + getListSize(head->next)

• C.

  E1: head == NULL
  E2: 1 + getListSize(head->next)

• D.

  E1: head->next == NULL
  E2: 1 + getListSize(head)

Hint:

Trace the recursive call on a short list (say 3 nodes) for each option and check both whether the recursion terminates and whether the returned count is correct.

Answer 1

The Correct Option is B

A different way to settle this is to reason by mathematical induction on the number of nodes n in the list, rather than tracing one specific example list.

Claim: with E1 = head->next==NULL and E2 = 1+getListSize(head->next) (option B), getListSize(head) returns exactly n for every list of n >= 1 nodes.

Base case, n=1: the single node's next field is NULL, so E1 is true immediately and the function returns 1, which is the correct size.

Inductive step: assume the claim holds for every list of length n-1 (n >= 2). For a list of n nodes starting at head, since n >= 2, head->next is not NULL, so E1 is false, and the function evaluates E2 = 1+getListSize(head->next). The sub list starting at head->next has exactly n-1 nodes, so by the inductive hypothesis getListSize(head->next) returns n-1, making the overall result 1+(n-1)=n, the correct size. By induction, option (B) is correct for every non-empty list length.

Now apply the same inductive lens to reject the other options. For option (A) and option (D), E2 always calls getListSize(head), i.e. the argument to the recursive call is identical to the current argument on every step where the base case is false. There is no smaller sub problem being solved, so the recursion depth is unbounded for n >= 2 and the call never terminates; these cannot be correct implementations of any function that returns a finite value. For option (C), redo the base case check: with E1 = head==NULL, the base case only fires one call past the true end of the list, so by the same inductive argument but shifted by one, getListSize on an n node list makes n recursive calls before the base case, returning n+1 instead of n, an off by one error for every list length, so option (C) can never be correct either.

Since induction confirms option (B) is exactly correct for all n, and shows options (A) and (D) never terminate while option (C) is always off by one, option (B) is the unique valid choice.$$ \boxed{\text{Option (B)}} $$