chapter
    Python Functions and Recursion Short Notes for GATE DA

    Python Functions and Recursion short notes for GATE DA: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    python functions and recursion short notes

    Systematic Tracing Protocol

    Systematic Tracing Protocol

    5-Step Trace Method

    1. Box Creation: Draw rectangle for each call. Header: func(args)
    2. Local Init: Write initial assignments (ans=1, i=0) inside box
    3. Call Descent: On recursive call, draw downward arrow. Pause current box.
    4. Base Return: At base case, write return value on upward arrow
    5. Resume & Compute: Substitute returned value into parent's pending expression. Continue execution in parent box.

    Notation Convention

    Use subscript to distinguish frames:

    This prevents variable collision confusion during manual trace.

    Return Value Aggregation vs Mutable State

    Return Value Aggregation vs Mutable State

    Pattern A: Return Aggregation
    ans = 1
for child in children:
  ans += func(child)
return ans
    • Pure, predictable, standard
    • Requires stack space proportional to depth
    Pattern B: Mutable External State
    global total
total += 1
for child in children:
  func(child)
    • Rarely tested directly
    • Side effects make tracing error-prone
    Exam Rule: Unless global or nonlocal is explicit, assume Pattern A. Local variables do NOT persist across recursive calls.

    The 'Shared Variable' Illusion

    The 'Shared Variable' Illusion

    Common Misconception: "Variable ans keeps accumulating across recursive calls."
    Reality Check: 
    def f(n):
  x = 0          # <- NEW x created EVERY call
  if n == 0: 
    return x
  x += f(n-1)    # <- Uses CHILD'S return, not child's x
  return x

    Diagnostic Questions

    1. Is there a global / nonlocal keyword? No Variable is local
    2. Is the variable assigned before recursive call? Yes Reset per frame
    3. Does the recursive call appear on RHS of assignment? Yes Return-value pattern
    Mnemonic: "Local = Limited to this call"

    2 more cards in this chapter

    Try a question

    Answer it here to see how it works. Nothing is recorded until you sign in.

    Question 1
    Level 1: Warm-up

    A recursive function f(n) contains a local variable x initialized to 0. If the initial call is f(3) and it makes recursive calls f(2), f(1), and f(0) in a single linear chain, how many distinct, isolated copies of the local variable x are created in total across all frames?

    Question 2
    Level 1: Warm-up

    According to the mental model of stack frames as isolated worlds, if a parent function initializes x = 10 and then calls a child function that modifies its own local x = 20, what is the value of x in the parent frame when the child returns?

    Question 3
    Level 1: Warm-up

    According to the mental model of stack frames as isolated worlds, if a recursive function f(n) makes a linear chain of calls from f(4) down to the base case f(0), how many distinct parent states are frozen at their call sites while the base case is executing?

    Question 4
    Level 1: Warm-up

    According to the mental model of stack frames as isolated worlds, parent state is frozen at the call site. If f(3) calls f(2), which then calls f(1), at the exact moment f(1) is executing its first line, how many distinct frames have their state frozen at a call site?

    Question 5
    Level 1: Warm-up

    The Systematic Tracing Protocol outlines specific steps for manual tracing of recursive functions. When a recursive call is encountered, the steps to handle the child frame must be performed in a strict order.

    Rank the following actions in the exact order they should be performed:

    P: Substitute the returned value into the parent's pending expression.

    Q: Draw a downward arrow to a new box and pause the current one.

    R: Write initial assignments inside the new box.

    S: Draw a rectangle for the new function call.

    Question 6
    Level 1: Warm-up

    Which of the following statements is strictly true regarding the Systematic Tracing Protocol for recursive functions?

    Question 7
    Level 1: Warm-up

    Consider the following Python function:

    ```python

    def s(n):

    if n == 0:

    return 1

    return 2 * s(n - 1)

    ```

    Rank the following function calls in increasing order of their return values:

    P: s(2), Q: s(0), R: s(3), S: s(1)

    Question 8
    Level 1: Warm-up

    When applying the Systematic Tracing Protocol to a linear recursive function f(n) that calls f(n-1), what is the maximum number of simultaneously paused stack frames when the base case f(0) is reached, given the initial call was f(4)?

    Question 9
    Level 1: Warm-up

    Consider the two patterns for accumulating results in recursion: Pattern A (Return Aggregation) and Pattern B (Mutable External State). Which of the following statements is strictly true regarding Pattern A?

    Question 10
    Level 1: Warm-up

    In the Systematic Tracing Protocol's 5-Step Trace Method, what is the maximum number of steps completed before you 'Resume & Compute' in the parent box?

    Free preview ends here

    Login to view the complete short 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

    Python Functions and Recursion Short Notes for GATE DA

    Python Functions and Recursion short notes for GATE DA: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    Systematic Tracing Protocol

    Systematic Tracing Protocol

    5-Step Trace Method

    1. Box Creation: Draw rectangle for each call. Header: func(args)
    2. Local Init: Write initial assignments (ans=1, i=0) inside box
    3. Call Descent: On recursive call, draw downward arrow. Pause current box.
    4. Base Return: At base case, write return value on upward arrow
    5. Resume & Compute: Substitute returned value into parent's pending expression. Continue execution in parent box.

    Notation Convention

    Use subscript to distinguish frames:

    This prevents variable collision confusion during manual trace.

    Return Value Aggregation vs Mutable State

    Return Value Aggregation vs Mutable State

    Pattern A: Return Aggregation
    ans = 1
for child in children:
  ans += func(child)
return ans
    • Pure, predictable, standard
    • Requires stack space proportional to depth
    Pattern B: Mutable External State
    global total
total += 1
for child in children:
  func(child)
    • Rarely tested directly
    • Side effects make tracing error-prone
    Exam Rule: Unless global or nonlocal is explicit, assume Pattern A. Local variables do NOT persist across recursive calls.

    The 'Shared Variable' Illusion

    The 'Shared Variable' Illusion

    Common Misconception: "Variable ans keeps accumulating across recursive calls."
    Reality Check: 
    def f(n):
  x = 0          # <- NEW x created EVERY call
  if n == 0: 
    return x
  x += f(n-1)    # <- Uses CHILD'S return, not child's x
  return x

    Diagnostic Questions

    1. Is there a global / nonlocal keyword? No Variable is local
    2. Is the variable assigned before recursive call? Yes Reset per frame
    3. Does the recursive call appear on RHS of assignment? Yes Return-value pattern
    Mnemonic: "Local = Limited to this call"

    Linear vs Tree Recursion: Trace Complexity

    Linear vs Tree Recursion: Trace Complexity

    FeatureLinear RecursionTree Recursion
    Calls per frame12 or more
    Trace shapeVertical chainBranching tree
    Stack depth
    Total calls
    Examplefact(n)fib(n)
    Exam focusReturn propagationCounting nodes / stack ops
    Exam Tip: If question asks "maximum stack size", answer = depth. If asks "number of function calls", answer = total nodes. Read carefully.

    Python Functions and Recursion: Solved Questions with Step-by-Step Explanations (10 Problems)

    Question 1 · Programming, Data Structures and Algorithms MCQ

    A recursive function f(n) contains a local variable x initialized to 0. If the initial call is f(3) and it makes recursive calls f(2), f(1), and f(0) in a single linear chain, how many distinct, isolated copies of the local variable x are created in total across all frames?

    1. A.

      1

    2. B.

      3

    3. C.

      4

    4. D.

      5

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: Every recursive call creates a new, isolated stack frame with its own local variables.

    Step 1: Identify the sequence of function calls: f(3), f(2), f(1), f(0).

    Step 2: Count the total number of function invocations in this chain. There are 4 calls in total.

    Step 3: Apply the mental model of stack frames. Each of the 4 calls creates a distinct stack frame.

    Step 4: Since x is a local variable initialized inside the function, a new, isolated copy of x is created in each of the 4 frames.

    Step 5: The total number of distinct copies is 4.

    Answer: C

    Question 2 · Programming, Data Structures and Algorithms MCQ

    According to the mental model of stack frames as isolated worlds, if a parent function initializes x = 10 and then calls a child function that modifies its own local x = 20, what is the value of x in the parent frame when the child returns?

    1. A.

      20

    2. B.

      0

    3. C.

      10

    4. D.

      30

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: Every recursive call creates a new, isolated stack frame with its own local variables. Changes in the child do not affect the parent.

    Step 1: Identify the mental model: Stack frames are isolated worlds.

    Step 2: The parent frame initializes its local x = 10.

    Step 3: The parent calls the child function, which creates a new, separate stack frame.

    Step 4: The child frame initializes its own local x = 20. This does not affect the parent's x.

    Step 5: When the child returns, the parent frame resumes. Its local x is still exactly what it was before the call: 10.

    Answer: C

    Question 3 · Programming, Data Structures and Algorithms MCQ

    According to the mental model of stack frames as isolated worlds, if a recursive function f(n) makes a linear chain of calls from f(4) down to the base case f(0), how many distinct parent states are frozen at their call sites while the base case is executing?

    1. A.

      3

    2. B.

      4

    3. C.

      5

    4. D.

      6

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: Every recursive call creates a new, isolated stack frame. The parent state is frozen at the call site until the child returns.

    Step 1: Identify the sequence of function calls: f(4), f(3), f(2), f(1), f(0).

    Step 2: Understand the state of each frame when f(0) is executing.

    Step 3: f(0) is the currently executing (active) frame. It is not frozen; it is running.

    Step 4: The frames f(4), f(3), f(2), and f(1) have all made recursive calls and are waiting for their children to return.

    Step 5: Therefore, their parent states are frozen at their respective call sites.

    Step 6: Count the frozen frames: 4.

    Answer: B

    Question 4 · Programming, Data Structures and Algorithms MCQ

    According to the mental model of stack frames as isolated worlds, parent state is frozen at the call site. If f(3) calls f(2), which then calls f(1), at the exact moment f(1) is executing its first line, how many distinct frames have their state frozen at a call site?

    1. A.

      1

    2. B.

      2

    3. C.

      3

    4. D.

      0

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: Every recursive call creates a new, isolated stack frame. The parent state is frozen at the call site until the child returns.

    Step 1: Identify the sequence of function calls: f(3) calls f(2), which calls f(1).

    Step 2: Understand the state of each frame when f(1) is executing its first line.

    Step 3: f(1) is the currently executing (active) frame. It is not frozen; it is running.

    Step 4: The frame f(3) made a call to f(2) and is waiting. Its state is frozen at that call site.

    Step 5: The frame f(2) made a call to f(1) and is waiting. Its state is frozen at that call site.

    Step 6: Count the frozen frames: f(3) and f(2). Total = 2.

    Answer: B

    Question 5 · Programming, Data Structures and Algorithms MCQ

    The Systematic Tracing Protocol outlines specific steps for manual tracing of recursive functions. When a recursive call is encountered, the steps to handle the child frame must be performed in a strict order.

    Rank the following actions in the exact order they should be performed:

    P: Substitute the returned value into the parent's pending expression.

    Q: Draw a downward arrow to a new box and pause the current one.

    R: Write initial assignments inside the new box.

    S: Draw a rectangle for the new function call.

    1. A.

      S, R, Q, P

    2. B.

      Q, S, R, P

    3. C.

      S, Q, R, P

    4. D.

      R, S, Q, P

    Correct Answer:

    A

    Step-by-Step Solution

    Key idea: The protocol enforces a strict visual and logical sequence to prevent state confusion.

    Step 1: First, you must create the visual container for the new frame. Draw a rectangle for the new call (S).

    Step 2: Next, establish the local state of this new frame. Write initial assignments inside the box (R).

    Step 3: Then, formally transition control. Draw a downward arrow to the new box and pause the current one (Q).

    Step 4: Finally, when the child returns, resume the parent. Substitute the returned value into the parent's pending expression (P).

    Correct order: S, R, Q, P.

    Answer: A

    Question 6 · Programming, Data Structures and Algorithms MCQ

    Which of the following statements is strictly true regarding the Systematic Tracing Protocol for recursive functions?

    1. A.

      The 'Resume & Compute' step can be performed before the base case returns a value.

    2. B.

      Local variable initializations must be written inside the box after the recursive call is made.

    3. C.

      The notation convention uses subscripts to distinguish frames and prevent variable collision.

    4. D.

      The downward arrow represents the return value propagating from the child to the parent.

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: The Systematic Tracing Protocol has strict rules for visual representation to avoid state confusion.

    Step 1: Evaluate option A. 'Resume & Compute' happens after the child returns. False.

    Step 2: Evaluate option B. Local initializations are step 2, written before the recursive call (step 3). False.

    Step 3: Evaluate option C. The protocol explicitly uses subscripts (e.g., ) to prevent variable collision across frames. True.

    Step 4: Evaluate option D. The downward arrow represents the call descent; the upward arrow represents the return value. False.

    Answer: C

    Question 7 · Programming, Data Structures and Algorithms MCQ

    Consider the following Python function:

    ```python

    def s(n):

    if n == 0:

    return 1

    return 2 * s(n - 1)

    ```

    Rank the following function calls in increasing order of their return values:

    P: s(2), Q: s(0), R: s(3), S: s(1)

    1. A.

      Q, P, S, R

    2. B.

      S, Q, P, R

    3. C.

      Q, S, R, P

    4. D.

      Q, S, P, R

    Correct Answer:

    D

    Step-by-Step Solution

    Key idea: This is a simple linear recursion that doubles at each step. Compute each value directly and sort.

    Step 1: s(0) = 1 (base case).

    Step 2: s(1) = .

    Step 3: s(2) = .

    Step 4: s(3) = .

    Step 5: Rank in increasing order: Q(1), S(2), P(4), R(8).

    Common trap: Ignoring the constraint that the base case is (not ) and miscomputing, or swapping P and S by computing instead of .

    Verification: The function computes . Values: . Increasing order: Q, S, P, R.

    Answer: D

    Question 8 · Programming, Data Structures and Algorithms MCQ

    When applying the Systematic Tracing Protocol to a linear recursive function f(n) that calls f(n-1), what is the maximum number of simultaneously paused stack frames when the base case f(0) is reached, given the initial call was f(4)?

    1. A.

      3

    2. B.

      4

    3. C.

      5

    4. D.

      6

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: In the tracing protocol, a frame is "paused" when it makes a recursive call and waits for the child to return. The currently executing frame is "active", not paused.

    Step 1: Trace the call sequence from the initial call f(4) down to the base case f(0).

    Step 2: The sequence of frames created is f(4), f(3), f(2), f(1), f(0). Total frames = 5.

    Step 3: Identify the state of each frame when f(0) is executing.

    Step 4: f(0) is the currently executing (active) frame. It is not paused.

    Step 5: The frames f(4), f(3), f(2), and f(1) are all waiting for their children to return. They are paused.

    Step 6: Count the paused frames: 4.

    Answer: B

    Question 9 · Programming, Data Structures and Algorithms MCQ

    Consider the two patterns for accumulating results in recursion: Pattern A (Return Aggregation) and Pattern B (Mutable External State). Which of the following statements is strictly true regarding Pattern A?

    1. A.

      It requires the use of the global keyword to maintain state.

    2. B.

      It relies on a shared mutable list to accumulate values across frames.

    3. C.

      Each frame computes a partial result and returns it, requiring no shared mutable state.

    4. D.

      It uses less stack space than Pattern B because it avoids creating new frames.

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: Pattern A (Return Aggregation) is the pure, standard form of recursion where results are passed back up the call chain via return values.

    Step 1: Recall the definition of Pattern A. It uses local variables to compute partial results and returns them to the parent frame.

    Step 2: Evaluate Option A. Pattern A does not use global or nonlocal; that is Pattern B.

    Step 3: Evaluate Option B. Pattern A does not rely on shared mutable state like lists; it uses immutable return values.

    Step 4: Evaluate Option C. This perfectly describes Pattern A: each frame computes a partial result and returns it, with no shared mutable state.

    Step 5: Evaluate Option D. Pattern A still creates a new stack frame for every recursive call, so it does not avoid creating new frames.

    Answer: C

    Question 10 · Programming, Data Structures and Algorithms MCQ

    In the Systematic Tracing Protocol's 5-Step Trace Method, what is the maximum number of steps completed before you 'Resume & Compute' in the parent box?

    1. A.

      5

    2. B.

      6

    3. C.

      3

    4. D.

      4

    Correct Answer:

    D

    Step-by-Step Solution

    Key idea: The Systematic Tracing Protocol consists of exactly 5 sequential steps. "Resume & Compute" is the final step.

    Step 1: Recall the 5 steps of the protocol: 1. Box Creation, 2. Local Init, 3. Call Descent, 4. Base Return, 5. Resume & Compute.

    Step 2: Identify the target step: "Resume & Compute" is Step 5.

    Step 3: Count the number of steps completed <b>before</b> Step 5.

    Step 4: Steps 1, 2, 3, and 4 are completed before Step 5 begins.

    Step 5: The maximum number of steps completed before resuming is 4.

    Answer: D

    More short notes in this unit