chapter
    Recursion and Recursive Program Analysis Notes for GATE CS

    Recursion and Recursive Program Analysis notes for GATE CS: 36 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questio

    recursion and recursive program analysis notes

    Boundary and Scope of Recursive Traversal

    Boundary and Scope of Recursive Traversal

    This specification defines the boundary of recursive traversal. We restrict our focus to linear structures. You will analyze how a function reduces an array or transforms a string by delegating the remainder of the structure to a subsequent call.

    The anchor for our analysis is an array of eight integers containing four contiguous blocks of identical values: [4, 4, 1, 1, 1, 7, 2, 2]. We will use this structure to isolate the mechanics of state accumulation and deferred execution.

    Explain this more simply

    Think of a conveyor belt moving boxes past a scanner. The scanner processes the current box, then signals the next section of the belt to move the remaining boxes. Recursive traversal operates identically: the function processes the current element, then delegates the rest of the array to the next recursive call.

    Go one level deeper

    Linear recursion is strictly bounded by the size of the input. Unlike tree or graph recursion, there is only one recursive call per invocation. This guarantees that the recursion depth is exactly N, making the call stack predictable and the execution path a single, unbranching line of descent followed by a single line of ascent.

    Pointer Arithmetic in Recursive Steps

    When passing an array to a recursive call, the standard mechanism is pointer arithmetic. If S is a pointer to the first element of an integer array, the expression S+1 does not add one to the value of the first element. It advances the memory address by the size of one integer.

    Consequently, the recursive call f(S+1, size-1) shifts the view of the array forward by one element while reducing the tracked size. This is the recursive equivalent of incrementing an index in an iterative loop.

    S[0]
    S[1]
    S[2]
    S[3]

    S+1 moves the pointer to the second box. The data inside the boxes does not change.

    Explain this more simply

    Imagine a row of mailboxes. S points to mailbox 0. S+1 does not change the mail inside mailbox 0; it simply moves your physical position to point at mailbox 1. The recursive function is just a person walking down the row, looking at one mailbox at a time.

    Go one level deeper

    Misinterpreting this shift as value addition is a primary source of error. In C, S+1 relies on the base type of the pointer. If S is a char pointer, S+1 advances by one byte. If S is an int pointer, it advances by four bytes. The compiler handles the scaling, but the programmer must understand that the array view shifts, not the underlying data.

    Tracing Immediate State Accumulation

    Consider a function count_blocks(int S[], int n) that returns the number of contiguous blocks of identical elements. The base case is n == 0, returning 0. If n == 1, it returns 1. For n > 1, if S[0] != S[1], it returns 1 + count_blocks(S+1, n-1). Otherwise, it returns count_blocks(S+1, n-1). Trace this function on the anchor array [4, 4, 1, 1, 1, 7, 2, 2].

    The immediate instinct is to scan the array visually, count the transitions between different numbers, and guess the answer is 4. This feels correct because the logic is simple, but it bypasses the mechanical trace required to verify the pointer shifts and base cases.

    Relying on visual scanning fails when the array contains subtle boundary conditions, such as a single-element block at the end. The stem signals a need for mechanical tracing by providing the exact recursive logic. If you do not trace the pointer S+1 and the size n-1, you will miss how the function handles the final elements.

    1. count_blocks([4, 4, 1, 1, 1, 7, 2, 2], 8): S[0] == S[1]. Returns count_blocks([4, 1, 1, 1, 7, 2, 2], 7).
    2. count_blocks([4, 1, 1, 1, 7, 2, 2], 7): S[0] != S[1]. Returns 1 + count_blocks([1, 1, 1, 7, 2, 2], 6).
    3. count_blocks([1, 1, 1, 7, 2, 2], 6): S[0] == S[1]. Returns count_blocks([1, 1, 7, 2, 2], 5).
    4. count_blocks([1, 1, 7, 2, 2], 5): S[0] == S[1]. Returns count_blocks([1, 7, 2, 2], 4).
    5. count_blocks([1, 7, 2, 2], 4): S[0] != S[1]. Returns 1 + count_blocks([7, 2, 2], 3).
    6. count_blocks([7, 2, 2], 3): S[0] != S[1]. Returns 1 + count_blocks([2, 2], 2).
    7. count_blocks([2, 2], 2): S[0] == S[1]. Returns count_blocks([2], 1).
    8. count_blocks([2], 1): Base case n == 1. Returns 1.

    Unwinding: Step 7 returns 1. Step 6 returns 1 + 1 = 2. Step 5 returns 1 + 2 = 3. Step 4 returns 3. Step 3 returns 3. Step 2 returns 1 + 3 = 4. Step 1 returns 4.

    Verification: The array has 4 blocks. The trace confirms the function correctly identifies them.

    Ranker inspection: The function simply counts the number of times S[i] != S[i+1] and adds 1 for the final block. You can solve this in O(1) mental time by just counting transitions in the array, bypassing the recursion entirely.

    33 more cards in this chapter

    Free preview ends here

    Login to view the complete notes

    Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

    Login to continueSee plans
    Why MastersUp

    Personalised first. High quality throughout.

    Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

    Built around you, not around a syllabus PDF

    Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

    Revision that hits your weak spots

    We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

    Questions calibrated to the real exam

    Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

    Notes written for recall, not for volume

    Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

    One place for everything

    Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

    Honest progress

    No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

    Unlock the whole course

    Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

    View all plansStart free

    Recursion and Recursive Program Analysis Notes for GATE CS

    Recursion and Recursive Program Analysis notes for GATE CS: 36 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    Boundary and Scope of Recursive Traversal

    Boundary and Scope of Recursive Traversal

    This specification defines the boundary of recursive traversal. We restrict our focus to linear structures. You will analyze how a function reduces an array or transforms a string by delegating the remainder of the structure to a subsequent call.

    The anchor for our analysis is an array of eight integers containing four contiguous blocks of identical values: [4, 4, 1, 1, 1, 7, 2, 2]. We will use this structure to isolate the mechanics of state accumulation and deferred execution.

    Explain this more simply

    Think of a conveyor belt moving boxes past a scanner. The scanner processes the current box, then signals the next section of the belt to move the remaining boxes. Recursive traversal operates identically: the function processes the current element, then delegates the rest of the array to the next recursive call.

    Go one level deeper

    Linear recursion is strictly bounded by the size of the input. Unlike tree or graph recursion, there is only one recursive call per invocation. This guarantees that the recursion depth is exactly N, making the call stack predictable and the execution path a single, unbranching line of descent followed by a single line of ascent.

    Pointer Arithmetic in Recursive Steps

    When passing an array to a recursive call, the standard mechanism is pointer arithmetic. If S is a pointer to the first element of an integer array, the expression S+1 does not add one to the value of the first element. It advances the memory address by the size of one integer.

    Consequently, the recursive call f(S+1, size-1) shifts the view of the array forward by one element while reducing the tracked size. This is the recursive equivalent of incrementing an index in an iterative loop.

    S[0]
    S[1]
    S[2]
    S[3]

    S+1 moves the pointer to the second box. The data inside the boxes does not change.

    Explain this more simply

    Imagine a row of mailboxes. S points to mailbox 0. S+1 does not change the mail inside mailbox 0; it simply moves your physical position to point at mailbox 1. The recursive function is just a person walking down the row, looking at one mailbox at a time.

    Go one level deeper

    Misinterpreting this shift as value addition is a primary source of error. In C, S+1 relies on the base type of the pointer. If S is a char pointer, S+1 advances by one byte. If S is an int pointer, it advances by four bytes. The compiler handles the scaling, but the programmer must understand that the array view shifts, not the underlying data.

    Tracing Immediate State Accumulation

    Consider a function count_blocks(int S[], int n) that returns the number of contiguous blocks of identical elements. The base case is n == 0, returning 0. If n == 1, it returns 1. For n > 1, if S[0] != S[1], it returns 1 + count_blocks(S+1, n-1). Otherwise, it returns count_blocks(S+1, n-1). Trace this function on the anchor array [4, 4, 1, 1, 1, 7, 2, 2].

    The immediate instinct is to scan the array visually, count the transitions between different numbers, and guess the answer is 4. This feels correct because the logic is simple, but it bypasses the mechanical trace required to verify the pointer shifts and base cases.

    Relying on visual scanning fails when the array contains subtle boundary conditions, such as a single-element block at the end. The stem signals a need for mechanical tracing by providing the exact recursive logic. If you do not trace the pointer S+1 and the size n-1, you will miss how the function handles the final elements.

    1. count_blocks([4, 4, 1, 1, 1, 7, 2, 2], 8): S[0] == S[1]. Returns count_blocks([4, 1, 1, 1, 7, 2, 2], 7).
    2. count_blocks([4, 1, 1, 1, 7, 2, 2], 7): S[0] != S[1]. Returns 1 + count_blocks([1, 1, 1, 7, 2, 2], 6).
    3. count_blocks([1, 1, 1, 7, 2, 2], 6): S[0] == S[1]. Returns count_blocks([1, 1, 7, 2, 2], 5).
    4. count_blocks([1, 1, 7, 2, 2], 5): S[0] == S[1]. Returns count_blocks([1, 7, 2, 2], 4).
    5. count_blocks([1, 7, 2, 2], 4): S[0] != S[1]. Returns 1 + count_blocks([7, 2, 2], 3).
    6. count_blocks([7, 2, 2], 3): S[0] != S[1]. Returns 1 + count_blocks([2, 2], 2).
    7. count_blocks([2, 2], 2): S[0] == S[1]. Returns count_blocks([2], 1).
    8. count_blocks([2], 1): Base case n == 1. Returns 1.

    Unwinding: Step 7 returns 1. Step 6 returns 1 + 1 = 2. Step 5 returns 1 + 2 = 3. Step 4 returns 3. Step 3 returns 3. Step 2 returns 1 + 3 = 4. Step 1 returns 4.

    Verification: The array has 4 blocks. The trace confirms the function correctly identifies them.

    Ranker inspection: The function simply counts the number of times S[i] != S[i+1] and adds 1 for the final block. You can solve this in O(1) mental time by just counting transitions in the array, bypassing the recursion entirely.

    Practice: Immediate Accumulation with Modified Input

    150sMCQ

    Using the count_blocks function defined previously, determine the exact integer value returned when the input array is [3, 3, 3, 5, 5, 8, 8, 8, 8, 9] and the initial size is 10.

    Full Solution

    The recognition trigger is immediate accumulation before the recursive call. The function counts contiguous blocks. The array has blocks of 3s, 5s, 8s, and 9s. That is exactly 4 blocks. The function will add 1 at the transitions from 3 to 5, 5 to 8, and 8 to 9, plus the base case return of 1 for the final element. Total is 4.

    Ranker inspection: The array has transitions at indices 2 (3 to 5), 4 (5 to 8), and 8 (8 to 9). That is 3 transitions. The number of blocks is always transitions + 1. Thus, 3 + 1 = 4.

    More notes in this unit