Computing what a recursive function returns via its recurrence; static and global variables inside recursion

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many moves does Tower of Hanoi need for n disks? from Lesson 2.1.3
• Code placed after a recursive call runs in which order? from Lesson 2.1.1
• How many times is a static local variable initialized? from Lesson 1.3.2

1 · The Hook

🎣

An exam question gives you a strange recursive function and asks for f(8). Tracing every call by hand can take dozens of steps. But if you write the function as a rule (“f of n is f of n − 1 plus twice f of n − 2”) you can fill a small table from the bottom up in a minute. The one thing that breaks this shortcut: variables shared between calls.

2 · Predict First

🤔

What does this print?

int f(int n)
{
    static int i = 1;
    if (n >= 5)
        return n;
    n = n + i;
    i++;
    return f(n);
}

int main(void)
{
    printf("%d\n", f(1));
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

7

i is static: one copy shared by all calls. n goes 1 → 2 (i = 1) → 4 (i = 2) → 7 (i = 3); 7 ≥ 5 returns 7.

The recurrence of a recursive function

A recurrence is an equation that defines a value in terms of the same function at smaller inputs, plus base values. For

int t(int n)
{
    if (n <= 2)
        return 1;
    return t(n - 1) + 2 * t(n - 2);
}

int main(void)
{
    printf("%d %d %d\n", t(3), t(5), t(8));
    return 0;
}

the recurrence is t(n) = t(n − 1) + 2·t(n − 2) for n > 2, with t(1) = t(2) = 1.

Solve bottom-up with a table

Instead of expanding the calls top-down, fill the values from the base cases upwards:

Output

3 11 85

This works only when the function is a pure function of its parameters: same input, same result.

Recognising a known formula

Some recurrences have closed forms worth recognising: f(n) = f(n − 1) + n → n(n + 1)/2; f(n) = 2f(n − 1) + 1 → 2ⁿ − 1; f(n) = f(n/2) + 1 → ⌊log₂ n⌋ + 1 (with f(1) = 1). Or the function computes something familiar:

int mystery(int a, int b)
{
    if (b == 0)
        return 0;
    if (b % 2 == 0)
        return mystery(a + a, b / 2);
    return mystery(a + a, b / 2) + a;
}

int main(void)
{
    printf("%d %d\n", mystery(6, 7), mystery(13, 10));
    return 0;
}

Output

42 130

mystery(a, b) doubles a while halving b and adds a whenever b is odd: it multiplies, a × b.

Static and global variables break the table method

A static or global variable is shared by all calls, so a call’s result depends on what earlier calls did. Then you must trace calls in the order they actually happen, updating the shared variable as you go. Remember that a static is initialized only once.

int count = 0;

int f(int n)
{
    count++;
    if (n <= 1)
        return 1;
    return f(n - 1) + f(n - 1);
}

int main(void)
{
    int r = f(4);
    printf("%d %d\n", r, count);
    return 0;
}

Output

8 15

f(n) = 2f(n − 1) = 2^n−1^ = 8, and count counts every call: 1 + 2 + 4 + 8 = 15.

Order matters with shared state

In return f(n − 1) + s; the value of s is read after f(n − 1) has returned (C’s rules here are subtle; to be safe, GATE-style questions are designed so that you trace the call first and then read the shared variable, as the compiled program does).

4 · Visual

Tracing with a shared static (program in Predict First):

call    n on entry   test n >= 5   n = n + i      i after   next call
f(1)       1           no          1 + 1 = 2        2       f(2)
f(2)       2           no          2 + 2 = 4        3       f(4)
f(4)       4           no          4 + 3 = 7        4       f(7)
f(7)       7           yes  -> return 7  (passed back unchanged through every call)

Table method for t(n) = t(n-1) + 2 t(n-2), t(1) = t(2) = 1:
n    : 1  2  3  4   5   6   7   8
t(n) : 1  1  3  5  11  21  43  85

Shared variables force a call-by-call trace; pure recurrences allow a bottom-up table.

5 · Worked Examples

Example 1 Easy

What does this print?

int t(int n)
{
    if (n <= 2)
        return 1;
    return t(n - 1) + 2 * t(n - 2);
}

int main(void)
{
    printf("%d %d %d\n", t(3), t(5), t(8));
    return 0;
}

Solution

From the table: t(3) = 3, t(5) = 11, t(8) = 85.

Output

3 11 85

Example 2 Medium

What does this print?

int g(int x)
{
    static int s = 0;
    s = s + x;
    if (x == 0)
        return s;
    return g(x - 1) + s;
}

int main(void)
{
    printf("%d\n", g(3));
    return 0;
}

Solution

s is shared. g(3): s = 3, calls g(2): s = 5, calls g(1): s = 6, calls g(0): s = 6, returns 6. Back in g(1): 6 + s(6) = 12. g(2): 12 + 6 = 18. g(3): 18 + 6 = 24. (s stopped changing once the deepest call ran.)

Output

24

Example 3 GATE

What does this print?

int f(int n)
{
    static int r = 0;
    if (n <= 0)
        return 1;
    if (n > 3) {
        r = n;
        return f(n - 2) + 2;
    }
    return f(n - 1) + r;
}

int main(void)
{
    printf("%d\n", f(5));
    return 0;
}

Solution

f(5): 5 > 3, so r = 5, return f(3) + 2. f(3): not > 3, return f(2) + r. f(2) → f(1) + r → f(0) + r, and f(0) = 1. r is 5 throughout: f(1) = 6, f(2) = 11, f(3) = 16, f(5) = 18.

Output

18

6 · GATE Traps

⚠️

• A static inside a recursive function is shared by every call and initialized only once.
• With shared variables you cannot use a bottom-up table; trace in execution order.
• Base cases in a recurrence must match the code exactly (n ≤ 1 vs n == 1 vs n ≤ 0).
• Values passed back up unchanged (return f(n)) mean the final answer is the base-case value.
• Check whether the question counts calls, additions, or the returned value.

8 · Memory Hook

🧠

“Pure functions fill tables; shared variables need a diary.” Without statics, write f(1), f(2), f(3) … upwards. With a static, keep a diary of its value call by call.

9 · Connect the Dots

Lessons 2.1.1–2.1.4 can now predict any recursive program’s output, return value and number of calls. Counting steps exactly gets tedious for big inputs; what matters for comparing programs is how the count grows. Next lesson answers: how do we describe the growth of the work done by a program in one short expression?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markStatic

What does this print?

int f(int n)
{
    static int i = 1;
    if (n >= 5)
        return n;
    n = n + i;
    i++;
    return f(n);
}

int main(void)
{
    printf("%d\n", f(1));
    return 0;
}

Numerical answer: ________

Q2NAT2 marksStatic

What does this print?

int g(int x)
{
    static int s = 0;
    s = s + x;
    if (x == 0)
        return s;
    return g(x - 1) + s;
}

int main(void)
{
    printf("%d\n", g(3));
    return 0;
}

Numerical answer: ________

Q3NAT2 marksRecurrence

f(1) = 2 and f(n) = 3·f(n − 1) − 1 for n > 1. What is f(5)?

Numerical answer: ________

Q4MCQ1 markClosed form

int f(int a, int b) { if (b == 0) return 0; return a + f(a, b - 1); } returns:

• (A) b
• (B) a + b
• (C) a^b^
• (D) a × b

Q5MCQ2 marksGlobal counter

What does this print?

int count = 0;

int f(int n)
{
    count++;
    if (n <= 1)
        return 1;
    return f(n - 1) + f(n - 1);
}

int main(void)
{
    int r = f(4);
    printf("%d %d\n", r, count);
    return 0;
}

• (A) 8 8
• (B) 8 15
• (C) 16 15
• (D) 8 7

11 · Rule Card

• Write the recurrence: f(n) in terms of f(smaller) + base values copied exactly from the code.
• Pure functions: fill a table bottom-up.
• Known forms: f(n − 1) + n → n(n + 1)/2; 2f(n − 1) + 1 → 2ⁿ − 1; f(n/2) + 1 → ⌊log₂ n⌋ + 1.
• Static/global inside recursion: shared by all calls, initialized once; trace calls in execution order.
• return f(…) passes the base-case value up unchanged.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

recurrencebottom-up tableclosed formshared state in recursion (static/global)

13 · Answer Vault