GATE 2015 COMPUTER SCIENCE & INFORMATION TECH. – CS – C Programming | Q. 21 (Session – 2)

💻 GATE 2015 – C Programming | Question 21

Question Type: MCQ   |   Topic: Recursion and Character Pointers

void foo(char *a)
{
    if (*a && *a != ' ')
    {
        foo(a+1);
        putchar(*a);
    }
}

🔄 What is Recursion?

The given question involves recursion technique. Recursion is a technique in which a function calls itself to solve a problem step by step. Think of a computer searching through a folder and its sub-folders: one folder may contain another folder, which may contain more folders, so the same searching task is repeated for each folder until there are no more folders to explore. Similarly, a family tree contains parents, grandparents, great-grandparents, and so on, where the same idea can be repeated for each generation. In programming, recursion continues solving smaller versions of the same problem until a stopping condition is reached.

💻 Complete C Program – Try It Yourself

The GATE question gives only the recursive function. To test the program in an online or offline C compiler, we need to add the required header file, main() function, and input statement. Copy the complete program below and run it with the input ABCD EFGH.

#include <stdio.h>

void foo(char *a)
{
    if (*a && *a != ' ')
    {
        foo(a + 1);
        putchar(*a);
    }
}

int main()
{
    char str[100];

    printf("Enter a string: ");
    scanf("%[^\n]", str);

    printf("Output: ");
    foo(str);

    return 0;
}

⚠️ Important: Notice that the function stops when it encounters a space character. Therefore, the characters EFGH are never processed. The interesting part is that putchar(*a) comes after the recursive call, so the characters are printed while the recursive calls are returning.

🧩 Step 1: Understand the Function and Input

Before tracing the recursion, let us first understand what the function receives and where the pointer a is pointing.

void foo(char *a)
{
    if (*a && *a != ' ')
    {
        foo(a + 1);
        putchar(*a);
    }
}

A  B  C  D  _  E  F  G  H  \0
^
a

The function then executes foo(a + 1). This moves the pointer to the next character. The same process continues for A → B → C → D. When the pointer reaches the space after D, the condition becomes false and the recursion stops.

🔁 Step 2: Follow the Recursive Calls

The function keeps calling foo(a + 1) as long as *a is not '\0' and is not a space. Therefore, the pointer moves through the characters A → B → C → D.

*a && *a != ' '

➡️ So the recursive calls occur in this order:

*a == ' '

📚 What has happened to the call stack?

Each recursive call is placed on the call stack. At the space, no new recursive call is made. The stack has therefore grown up to the call for D.

foo("ABCD EFGH")
    └── foo("BCD EFGH")
         └── foo("CD EFGH")
              └── foo("D EFGH")
                   └── foo(" EFGH")   ← stops here

🔙 Step 3: Returning from the Recursive Calls

When the pointer reaches the space, the condition becomes false and that recursive call finishes. The function then starts returning one call at a time. Remember that putchar(*a) appears after the recursive call, so the character is printed only when that particular recursive call returns.

putchar(*a);

putchar(*a);

putchar(*a);

putchar(*a);

foo(a + 1);       /* recursive call */
putchar(*a);      /* executed after recursion returns */

🔎 Important Observation

The function never processes the characters after the first space. In this input, the space occurs immediately after ABCD.

When a reaches this space, *a != ' ' becomes false. Therefore, the if block is not executed and the recursion stops completely. It does not restart after the space.

🎯 Final Output

🖨️ What is putchar()?

putchar() is a C library function used to print one character on the screen. In our program, putchar(*a) prints the character currently pointed to by the pointer a.

putchar(character);

putchar('A');

putchar(*a);

🔴 Every recursive solution must have a
BASE CONDITION
to stop the recursion.

Library Books Stack Analogy to understand Recursion

void foo(char *a)
{
    if (*a && *a != ' ')
    {
        foo(a + 1);
        putchar(*a);
    }
}

foo("ABCD EFGH")      ← A
    foo("BCD EFGH")   ← B
        foo("CD EFGH") ← C
            foo("D EFGH") ← D
                foo(" EFGH") ← SPACE

Return from D → putchar('D') → D printed
Return from C → putchar('C') → C printed
Return from B → putchar('B') → B printed
Return from A → putchar('A') → A printed

foo(" EFGH")

foo(" EFGH")  → returns
foo("D EFGH") → putchar('D') → prints D
foo("CD EFGH") → putchar('C') → prints C
foo("BCD EFGH") → putchar('B') → prints B
foo("ABCD EFGH") → putchar('A') → prints A