"Programming in C & Recursion" — Practice

Question 1

If p is an int pointer holding address 2000 and an int occupies 4 bytes, what address does p + 5 hold?

Accepted Answer

B

Question 2

A function contains a static local variable initialised to 0 and incremented on each call. What does it print on the third call?

Accepted Answer

A

Question 3

In C, what is the effect of a function that takes two int parameters and swaps them internally?

Accepted Answer

C

Question 4

For int arr[10] on a machine with 4-byte integers and 8-byte pointers, state the values of sizeof(arr), sizeof(&arr), the byte difference between arr and arr+1, and between &arr and &arr+1.

Accepted Answer

Take each in turn, remembering that array decay has exactly two exceptions.

sizeof(arr) is one of them. Here the array name does not decay, so the result is the size of the whole array: 10 elements times 4 bytes = 40 bytes.

sizeof(&arr) is the size of a pointer, since the address-of operator yields a pointer to array and all object pointers have the same size on this machine: 8 bytes.

For arr + 1, the array name decays to a pointer to the first element, which is an int pointer. Adding 1 advances by one int, so the byte difference is 4.

For &arr + 1, the operand is a pointer to array of 10 ints, so adding 1 advances by one whole array. The byte difference is 40.

The pattern worth extracting is that the type of the pointer decides the stride in every case, and the two exceptions to decay are precisely where the type differs from a plain element pointer.

Question 5

A function prints its parameter, then calls itself with the parameter reduced by 1, with a base case at 0. A second function is identical except the print comes after the call. Trace both for n = 4 and explain the difference.

Accepted Answer

First function, printing before the call. The call with 4 prints 4 immediately, then calls with 3, which prints 3, and so on down to the base case.

Output: 4 3 2 1.

Second function, printing after the call. The call with 4 immediately calls with 3 without printing anything. That calls with 2, which calls with 1, which calls with 0. The base case returns without printing.

Now the stack unwinds. The frame holding 1 resumes and prints 1. The frame holding 2 prints 2. Then 3, then 4.

Output: 1 2 3 4.

The explanation is that work placed before the recursive call executes on the way down, while the parameter is descending, and work placed after it executes on the way back up, in reverse order of the descent.

A second consequence follows. The first function is tail recursive, since nothing remains to be done after the call, and a compiler may convert it to a loop with constant stack usage. The second is not, because each frame must survive until its print statement runs, so the stack genuinely grows to depth n.

Question 6

Identify what is wrong with a function that declares a local integer array, fills it, and returns a pointer to it. Give three correct alternatives.

Accepted Answer

The array lives in the function's stack frame. When the function returns, that frame is released and the memory becomes available for the next call to use.

The returned pointer therefore refers to memory that no longer belongs to anyone, and dereferencing it is undefined behaviour.

What makes this especially dangerous is that it usually appears to work. Immediately after the return the bytes are often untouched, so a print right after the call may show the correct values. The first unrelated function call reuses that stack space and the data changes at an unpredictable moment, producing a bug that seems intermittent.

Three correct alternatives. First, allocate on the heap with a dynamic allocation call, which gives memory that outlives the frame, at the cost of making the caller responsible for freeing it. Second, have the caller provide the storage and pass a pointer to it as a parameter, so the lifetime is the caller's concern and no allocation is needed. Third, declare the array static, which moves it to the data segment so the pointer stays valid.

The third has a hidden cost worth noting: every call returns the same address, so a second call overwrites the first call's data and the function is not reentrant.

Question 7

A function returns n when n is at most 1, and otherwise returns the sum of calls on n-1 and n-2. Determine the total number of calls for n = 6 and the maximum stack depth.

Accepted Answer

Let C(n) be the total number of invocations including the initial one.

Base cases: C(0) = 1 and C(1) = 1, since each returns immediately.

Recursive case: C(n) = 1 + C(n-1) + C(n-2), counting the current call plus everything its two children generate.

C(2) = 1 + 1 + 1 = 3.
C(3) = 1 + 3 + 1 = 5.
C(4) = 1 + 5 + 3 = 9.
C(5) = 1 + 9 + 5 = 15.
C(6) = 1 + 15 + 9 = 25.

So the function is called 25 times.

The maximum stack depth is a different quantity entirely. At any instant the stack holds one root-to-current chain, not the whole tree. The longest chain follows the n-1 branch repeatedly: 6, 5, 4, 3, 2, 1, giving depth 6.

So the time complexity is exponential while the space complexity is only linear in n.

The distinction matters because calls that have already returned release their frames. A common error is to assume that exponentially many calls imply exponential space, when in fact the tree is explored depth-first and only one path is ever resident.

Question 8

An array is declared as int a[4][6] with base address 1000 and 4-byte integers, stored in row-major order. Compute the address of a[2][3], and state how the answer would change under column-major storage.

Accepted Answer

In row-major order, all of row 0 is stored first, then all of row 1, and so on. Reaching element a[i][j] therefore requires skipping i complete rows of C elements each, then j further elements.

Address = base + (i times C + j) times element size.

Substituting: 1000 + (2 times 6 + 3) times 4 = 1000 + 15 times 4 = 1000 + 60 = 1060.

Under column-major storage the roles reverse: all of column 0 comes first, then column 1, and so on. Reaching a[i][j] requires skipping j complete columns of R elements each, then i further elements.

Address = base + (j times R + i) times element size.

Substituting: 1000 + (3 times 4 + 2) times 4 = 1000 + 14 times 4 = 1000 + 56 = 1056.

Two points are worth extracting. C uses row-major order, so the first computation is the one that applies to C code, while some other languages use column-major and the distinction changes the answer. And the ordering has a real performance consequence: traversing a row-major array along rows walks contiguous memory and uses each cache line fully, while traversing along columns strides across the array and can miss on nearly every access.

Question 9

A procedure takes two parameters and executes: first parameter gets first parameter plus 1, then second parameter gets second parameter times 2. It is called with the same variable x, initially 5, as both arguments. Give the final value of x under call by value, call by reference, and call by value-result.

Accepted Answer

Call by value. The procedure receives two independent copies, both holding 5. It sets the first copy to 6 and the second to 10, then both copies are discarded on return.

The caller's x is untouched, so x remains 5.

Call by reference. Both parameters are bound to the same variable x, so every operation acts on x directly.

The first statement sets x to 5 plus 1 = 6. The second statement then reads the current value of x, which is now 6, and doubles it to 12.

So x becomes 12.

Call by value-result. Both parameters are copies on entry, both holding 5. The procedure sets the first copy to 6 and the second copy to 10, operating on independent copies exactly as in call by value.

On exit, both copies are written back to x. The order of write-back determines the result: if the parameters are copied back left to right, x receives 6 and then 10, ending at 10. If right to left, x ends at 6.

The answer is therefore 10 or 6 depending on the write-back order, which most language definitions leave unspecified.

This three-way divergence is exactly why aliasing — passing the same variable twice — is the standard test case for distinguishing the mechanisms, and why value-result is considered fragile.

Practice — "Programming in C & Recursion"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities