Study guide
6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
Praxis Computer Science 5652
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode
1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy
2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects
2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations
3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security
3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage
4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation
4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing
5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range
6 Chapter 6: Algorithms: Searching, Sorting, and Recursion
6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions
7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra
8 Chapter 8: Programming: Selection, Iteration, and Writing Code
8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code
9 Chapter 9: Programming: Procedures, Arrays, and Data Structures
9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)
10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality
10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback
11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs
11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs
12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design
12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding
13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption
13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs
14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection
14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing
15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments
15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored
16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity
16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs
6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
Key Takeaways Explain This Topic AI
A correct recursive procedure has at least one base case that returns without recursing and a recursive call that moves the input toward a base case.
Each call gets its own stack frame with its own parameters and local variables; missing or unreachable base cases cause infinite recursion and a stack overflow.
To trace recursion, list the calls down to the base case, then substitute return values back up in reverse order.
Naive recursive Fibonacci makes an exponential number of calls because it recomputes the same subproblems; fib(4) alone makes 9 calls.
Every recursive algorithm has an iterative equivalent; simple linear recursions such as factorial become a loop with an accumulator.
Last updated: September 2026
What this competency asks
ETS asks you to understand simple recursive algorithms (for example, n factorial and the sum of the first n integers):
Trace simple recursive algorithms.
Provide missing steps in incomplete simple recursive algorithms.
Identify parts of a recursive algorithm, such as the base (stopping) condition and the recursive call.
Identify errors in simple recursive algorithms.
Identify an iterative algorithm that is equivalent to a recursive algorithm.
The discussion questions also ask you to analyze the number of recursive calls .
- Anatomy of a recursive procedure
- A recursive procedure calls itself on a smaller version of the same problem. int factorial ( int n )
- if ( n ≤ 1 )
- return 1 // base case
- else
- return n * factorial ( n - 1 ) // recursive call on a smaller input
- end if
- end factorial
- Part Role In factorial
- Base case (stopping condition) Answers the smallest input directly, without recursing n ≤ 1 returns 1
- Recursive call Solves a smaller instance factorial ( n - 1 )
- Progress toward the base case Guarantees the calls eventually stop n decreases by 1 each time
- Combining step Builds the answer from the smaller result n * …
- Tracing recursion: down, then up
Each call waits for the call it makes. Write the calls going down , then fill in return values coming back up .
- factorial ( 4 ) factorial(4) = 4 * factorial(3)
- factorial(3) = 3 * factorial(2)
- factorial(2) = 2 * factorial(1)
- factorial(1) = 1 ← base case
- factorial(2) = 2 * 1 = 2
- factorial(3) = 3 * 2 = 6
- factorial(4) = 4 * 6 = 24
Four calls are active at the deepest point, one stack frame per call. Each frame holds its own copy of n . When a call returns, its frame is removed and the caller resumes where it left off.
- Sum of the first n integers int sumTo ( int n )
- if ( n == 0 )
- return 0
- else
- return n + sumTo ( n - 1 )
- end if
- end sumTo
sumTo(4) = 4 + sumTo(3) = 4 + 3 + sumTo(2) = 4 + 3 + 2 + sumTo(1) = 4 + 3 + 2 + 1 + sumTo(0) = 4 + 3 + 2 + 1 + 0 = 10 . That takes 5 calls , for n = 4, 3, 2, 1, and 0.
Supplying a missing step
To fill in a missing recursive step, write the relationship between the answer for n and the answer for a smaller input. For example, suppose a procedure should return the product of the integers from 3 through n (for n ≥ 3): int prodFrom3 ( int n )
- if ( n == 3 )
- return 3
- else
- /* missing statement */
- end if
- end prodFrom3
The product from 3 to n equals n times the product from 3 to n − 1, so the missing statement is return n * prodFrom3 ( n - 1 ) . Check it with a small case: prodFrom3(5) = 5 × prodFrom3(4) = 5 × 4 × prodFrom3(3) = 5 × 4 × 3 = 60. Wrong choices typically recurse on the same n, which never ends, or jump too far, such as n - 3 , which skips the base case.
Finding errors
- Error Example Effect
- Missing base case return n + sumTo ( n - 1 ) with no if Infinite recursion, then a stack overflow
Base case never reached Calling factorial ( n + 1 ) , or testing n == 0 when n can be negative or can skip 0 Stack overflow
Wrong base value return 0 as the base case of factorial Every result becomes 0
Wrong combining step return n * sumTo ( n - 1 ) in a sum Computes a product (and returns 0, from the base case)
- No progress return f ( n ) Calls itself with the same input forever
- Counting calls: when recursion branches int fib ( int n )
- if ( n ≤ 1 )
- return n
- else
- return fib ( n - 1 ) + fib ( n - 2 )
- end if
- end fib
- Each non-base call makes two calls, so the calls form a tree: fib(4)
- / \
- fib(3) fib(2)
- / \ / \
- fib(2) fib(1) fib(1) fib(0)
- / \
- fib(1) fib(0)
Counting nodes gives 9 calls for fib(4). fib(2) is computed twice and fib(1) three times. The number of calls grows exponentially with n, roughly O(2ⁿ). Storing results that have already been computed ( memoization , O(n) extra memory) or building up from fib(0) with a loop reduces the time to O(n).
Recursion and iteration
Any recursive algorithm can be rewritten iteratively. Simple linear recursions translate directly into a loop with an accumulator : int factorialLoop ( int n )
- int result ← 1
- for ( int i ← 2; i ≤ n; i ← i + 1 )
- result ← result * i
- end for
- return result
- end factorialLoop
To check that an iterative version is equivalent , compare them on the base case, for example n = 0 or 1 (both should return 1), and on a small value such as 4 (both should return 24).
- Recursive Iterative
- Memory One stack frame per active call: O(depth) Usually O(1) extra
- Failure mode Stack overflow when too deep Infinite loop
- Natural fit Trees, divide-and-conquer, nested structures Simple counting and accumulation
Some languages, such as Scheme, guarantee tail-call optimization . When the recursive call is the very last action, the language reuses the current frame, so deep tail recursion does not overflow the stack. Many popular languages, including Java and Python, do not perform this optimization.
A recursive algorithm you already know
Binary search (Section 6.1) is naturally recursive. Search the middle, then call the same procedure on the left or right half, with low > high as the base case for "not found." Because it makes only one recursive call per level, it makes about log₂ n calls, not an exponential number.