Applied Information Technology Engineer Exam, Subject A, Part 6: Pseudocode, Recursion, Complexity, and State Transitions

Revised: 2026-10-20 Scope: Preparation for the 2026 exam, based on IPA’s “応用情報技術者試験（レベル3）シラバス Ver.7.2” (Applied Information Technology Engineer Examination, Level 3, Syllabus Ver.7.2) Notice: Exam scope and format can change, so always check IPA’s latest official information before you sit the exam. This article is a study aid and does not guarantee a pass. It was not written or endorsed by IPA.

Prerequisite: Part 5 gave an overview of search and sort algorithms and compared their complexity. This part does not repeat that material. It covers how to take any algorithm and trace it by hand, check that it stops, count its cost, and read it as a sequence of state changes.

---

1. Learning index and objectives

Section	Content	After reading, you should be able to
2	Terminology table	Move between the Korean, Japanese, and English terms
3	This article’s pseudocode notation	Tell assignment (←) from equality (=) and read loop bounds exactly
4	Tracing method, Example 1	Choose a checkpoint and fill in a trace table one row at a time
5	Loop termination, Example 2	Check initialization, condition, and update; trace the Euclidean algorithm
6	Recursion, Example 3	Trace calls (descent) and returns (unwinding) separately
7	Complexity, Example 4	Count exact executions and summarize them with Θ/O
8	State transitions, Example 5	Read a transition table and trace the states for an input string
9	Five original practice questions	Apply each of the five skills above to a question
10–13	Quick sheet, traps, self-check, review	Review the key points quickly and find weak spots

---

2. Terminology table

Korean	Japanese	English
의사코드	擬似言語（擬似コード）	pseudocode
대입	代入	assignment
같음 비교	等価比較（等しいかの比較）	equality comparison
조건	条件	condition
분기	分岐（選択）	branch
반복(루프)	繰返し（ループ）	loop
반복 1회(이터레이션)	繰返し1回分（反復）	iteration
반복 조건(계속 조건)	繰返し条件（継続条件）	loop condition
종료 조건	終了条件	termination condition
초기화	初期化	initialization
갱신	更新	update
추적표	トレース表	trace table
상태	状態	state
상태 전이	状態遷移	state transition
상태 전이표 / 상태 전이도	状態遷移表 / 状態遷移図	transition table / transition diagram
재귀 호출	再帰呼出し	recursive call
기저 사례(종료 사례)	基底部（再帰の終了条件）	base case
호출 스택	呼出しスタック（コールスタック）	call stack
반환값	戻り値（返却値）	return value
시간 계산량 / 공간(영역) 계산량	時間計算量 / 領域計算量	time complexity / space complexity
정확한 연산 횟수	正確な演算回数（実行回数）	exact operation count
빅오 표기	オーダー記法（O記法）	Big-O notation

---

3. Pseudocode notation used only in this article

The notation below was defined for this article’s explanations and practice questions. It is not claimed to match IPA’s official exam notation. Real exam questions may define symbols differently, and when they do, the question’s definition always wins.

Notation	Meaning
x ← e	Evaluate expression e, then store the value in variable x (assignment).
a = b	Test whether a equals b (true/false). This is not assignment.
≠, <, ≤, >, ≥	Comparison operators.
a div b	Integer quotient. Used only with non-negative integers here. Example: 7 div 2 = 3.
a mod b	Remainder of integer division. Used here only with non-negative a and positive b. Example: 48 mod 18 = 12.
for i ← a to b	Repeat with i running from a to b in steps of 1. Both ends are included. If a > b, the body never runs.
while condition	Pre-test loop: the condition is checked before every iteration, and the loop keeps going while it is true. If it is false at the start, the body runs 0 times.
if condition … else …	Run the first block if the condition is true, otherwise run the else block.
A[i]	Element i of array A. In this article, indexes start at 1 (A[1] is the first element).
return e	End the current call and pass the value of e back to the caller.
output e	Output the value of e.
Indentation	Statements at the same indentation depth form one block.

None of this article’s examples or questions use compound conditions such as and/or, so short-circuit evaluation is not assumed.

---

4. How to trace

Tracing by hand is not “roughly running it in your head”. It is recording by fixed rules. Following these steps cuts mistakes sharply.

1. Fix the initial state. Write every variable’s value before the loop starts in the first (initial) row.
2. Execute one statement (or one iteration) at a time. Don’t process several statements in your head at once.
3. Define a checkpoint and record only at that point. Example: “immediately after every statement in the loop body has run”. Decide first what moment each table row represents.
4. Keep old and new values separate. In total ← total + x, the x on the right is the value at the moment this statement runs. A later x ← 2 * x in the same iteration has not happened yet.
5. Record condition checks too. The point where the while condition becomes true or false decides how many iterations run.
6. Confirm the output and the final state. After the loop exits, write down separately what is output and each variable’s last value.

Example 1: Variable trace

x ← 1
total ← 0
while x ≤ 8
    total ← total + x
    x ← 2 * x
output total

Row meaning: iteration-k row = state immediately after both total ← total + x and x ← 2 * x have run in iteration k.

Row	x at check (condition x ≤ 8)	x after	total after
Initial	—	1	0
Iteration 1	1 ≤ 8 true	2	1 (= 0 + 1)
Iteration 2	2 ≤ 8 true	4	3 (= 1 + 2)
Iteration 3	4 ≤ 8 true	8	7 (= 3 + 4)
Iteration 4	8 ≤ 8 true	16	15 (= 7 + 8)
Exit check	16 ≤ 8 false	—	—

• Iterations: 4. Checkpoint rows (x, total): (2,1) → (4,3) → (8,7) → (16,15).
• Output: 15. Final state: x = 16, total = 15.
• Trap: the condition is ≤, so the body also runs when x = 8. Misreading it as < gives 3 iterations and output 7.

---

5. Loop termination

To make a while loop end as intended, check three things together.

• Initialization: Do the variables hold the right values before the loop?
• Condition: The condition after while is a continue condition. “When does it stop?” (the termination condition) is its negation. Example: the termination condition of while b ≠ 0 is b = 0. Writing the termination condition directly after while makes the loop never start or behave unexpectedly.
• Update (progress): Does every iteration make a change that moves the condition toward false?

Typical traps

• Off-by-one errors: mixing up < and ≤, or a start value of 0 versus 1, makes the loop run one time too many or too few. Check the iteration count by plugging in the first value, the last value, and the condition.
• Non-progress: if the update statement is missing, or the update changes a variable the condition doesn’t depend on, the loop never ends.

Intuition for a variant (ranking function): if you can find one integer value that strictly decreases every iteration and cannot drop below some lower bound while the loop continues, the loop must end after finitely many iterations. In Example 1, 9 − x goes 8, 7, 5, 1, and once it would fall below 1 (condition x ≤ 8 false) the loop stops. For the exam, a sense of “what shrinks every time?” is enough; a rigorous proof is not needed.

Example 2: Euclidean algorithm for (48, 18)

a ← 48
b ← 18
while b ≠ 0
    r ← a mod b
    a ← b
    b ← r
output a

Row meaning: iteration-k row = (a, b) immediately after all three statements of iteration k have run.

Row	Check (b ≠ 0)	r = a mod b (using old a, old b)	(a, b) after
Initial	—	—	(48, 18)
Iteration 1	18 ≠ 0 true	48 mod 18 = 12 (48 = 18×2 + 12)	(18, 12)
Iteration 2	12 ≠ 0 true	18 mod 12 = 6 (18 = 12×1 + 6)	(12, 6)
Iteration 3	6 ≠ 0 true	12 mod 6 = 0 (12 = 6×2 + 0)	(6, 0)
Exit check	0 ≠ 0 false	—	—

• State changes: (48,18) → (18,12) → (12,6) → (6,0). 3 iterations, output 6 (the greatest common divisor of 48 and 18).
• Why it terminates (variant): the remainder r always satisfies 0 ≤ r < b, so the new b is strictly smaller than the old b and never negative. A non-negative integer cannot decrease forever, so b = 0 is always reached.
• Trap: swapping a ← b and b ← r (running b ← r first) puts the new b into a and gives the wrong result. The temporary variable r exists to preserve the old value.

---

6. Recursion

A recursive function calls itself. When tracing, separate two phases.

1. Descent (calls): calls pile up until a base case is reached. Nothing has finished computing yet. Every call is “pending”.
2. Unwinding (returns): once the base case returns a value, the pending calls finish in reverse order, most recent first, and return.

Key rules:

• Every recursive path must make progress toward a base case. If any path’s argument doesn’t get closer to a base case, calls pile up forever.
• Each active call has its own parameters and local variables on the call stack. The n inside F(5) and the n inside F(3) are different variables.
• The call stack is last-in, first-out (LIFO), so return order is the reverse of call order.

Example 3: Calls and returns of F(5)

F(n):
    if n ≤ 1
        return 1
    else
        return n + F(n − 2)

Call (descent) order

Step	Call	n	Action	Stack depth (after call)
C1	F(5)	5	5 ≤ 1 false → 5 + F(3) pending	1
C2	F(3)	3	3 ≤ 1 false → 3 + F(1) pending	2
C3	F(1)	1	1 ≤ 1 true → base case	3

Return (unwinding) order

Step	Returning call	Computation	Return value
R1	F(1)	base case	1
R2	F(3)	3 + 1	4
R3	F(5)	5 + 4	9

• Expansion: F(5) = 5 + F(3) = 5 + 3 + F(1) = 5 + 3 + 1 = 9.
• Call order: F(5), F(3), F(1). Return order: F(1), F(3), F(5), with return values 1, 4, 9.
• Cost: for n ≥ 1, the number of calls is ⌊n/2⌋ + 1 (equivalently, ⌈(n + 1)/2⌉), roughly n/2, and each call does a constant amount of work. Complexity notation ignores constant factors (the 1/2), so time is Θ(n). For the same reason the largest number of calls on the stack at once (call-stack depth) is also Θ(n), which means Θ(n) extra space.
• This definition makes only one recursive call per call, so the number of calls is linear. A definition that makes two recursive calls inside one call has different complexity; don’t confuse the two.

---

7. Complexity

Complexity describes how the number of executions (or the memory used) grows with the input size n. It is not the elapsed time in seconds on a particular computer. Elapsed time depends on hardware, language, and implementation. How the execution count grows is a property of the algorithm itself.

Keep three levels apart.

Level	Meaning	Example
Exact count	How many times a given statement runs, exactly	n(n + 1)/2
Θ (theta)	Tight growth rate (bounded above and below), constant factors ignored	Θ(n²)
O (Big-O)	Upper bound (grows no faster than this), constant factors ignored	O(n²). O(n³) is also true, but loose

When an exam says “the complexity is O(…)”, it usually means the tightest upper bound, but remember that by definition O is an upper bound.

Example 4: Exact count for a triangular nested loop

count ← 0
for i ← 1 to n
    for j ← 1 to i
        count ← count + 1
output count

Counting convention: count the executions of count ← count + 1 (= the final value of count).

For n = 4, each row means “immediately after the inner loop of outer iteration i has finished”.

i	Inner j values	Executions this round	Running count
1	1	1	1
2	1, 2	2	3
3	1, 2, 3	3	6
4	1, 2, 3, 4	4	10

• General formula: 1 + 2 + … + n = n(n + 1)/2. For n = 4: 4×5/2 = 10.
• n(n + 1)/2 = n²/2 + n/2. Keeping the highest-order term and dropping the constant factor gives Θ(n²), and therefore O(n²).

Counting rules summary

• Sequential blocks add: block A followed by block B costs A + B, and the growth rate is the larger of the two. Example: n + n² → Θ(n²).
• Independent nested loops multiply: outer n iterations × inner m iterations (inner range independent of the outer variable) → n·m.
• Halving/doubling loops are logarithmic: a loop that does j ← 2 * j (or n ← n div 2) each time runs about log₂ n times → Θ(log n).
• Branches: an exact count uses the path actually taken. Worst-case complexity (Big-O) uses the most expensive branch.
• Space complexity: look at memory used beyond the input (auxiliary space). Example 4 uses only count, i, and j, so Θ(1). In recursion, the call stack also counts as space. F(n) in Example 3 uses Θ(n) stack space.

---

8. State transitions

The word “state” has two meanings.

• An algorithm’s variable state: the set of all variable values at a given moment. Example: (a, b) = (18, 12) in Example 2.
• A finite-state machine’s (finite automaton’s) state: one of a predefined, finite set of states. Example: “even (E)”, “odd (O)”.

In a finite-state machine, a transition means the next state is determined once the current state and the input symbol are known. Writing those rules as a table gives a transition table. Drawing them as circles and arrows gives a transition diagram.

Example 5: Parity automaton (is the number of 1s even?)

• States: E (the number of 1s read so far is even), O (odd). Start state E.
• Rules: input 0 → stay in the same state; input 1 → switch between E and O.

Transition table

Current state	Input 0	Input 1
E	E	O
O	O	E

Transition diagram (text form)

(start) → E
E --0--> E      E --1--> O
O --0--> O      O --1--> E

Trace for input 101101. Row meaning: both the state before reading symbol k and the state after reading it are recorded.

k	State before	Input symbol	State after
1	E	1	O
2	O	0	O
3	O	1	E
4	E	1	O
5	O	0	O
6	O	1	E

• State sequence: E → O → O → E → O → O → E.
• Final state E means the number of 1s in the input (four) has even parity.
• Trap: if you answer with only the “before” column, the last symbol’s effect is lost and you get E, O, O, E, O, O. Always check what a row means in the question.

---

9. Original practice questions (5)

All five questions below were written new for this article. No past exam questions were used or adapted. They use the article-only notation from Section 3.

Question 1 (variable trace)

What value of b is output when this pseudocode runs? (Checkpoint: immediately after all three statements in the loop body have run.)

a ← 3
b ← 0
k ← 1
while k ≤ 3
    b ← b + a * k
    a ← a − 1
    k ← k + 1
output b

1. 7
2. 18
3. 10
4. 4

Answer: 3 (10)

Trace table (a, b, k after each iteration):

Row	Check	Computation	a	b	k
Initial	—	—	3	0	1
Iteration 1	1 ≤ 3 true	b = 0 + 3×1 = 3	2	3	2
Iteration 2	2 ≤ 3 true	b = 3 + 2×2 = 7	1	7	3
Iteration 3	3 ≤ 3 true	b = 7 + 1×3 = 10	0	10	4
Exit	4 ≤ 3 false	—	—	—	—

• Option 1 (7): the value right after iteration 2. You get this by misreading ≤ as < and running only 2 iterations.
• Option 2 (18): computes 3×1 + 3×2 + 3×3, ignoring that a decreases.
• Option 3 (10): correct. Each statement runs in order using the values current at that moment.
• Option 4 (4): assumes a ← a − 1 runs before b is updated (2×1 + 1×2 + 0×3 = 4).

Question 2 (loop termination, off-by-one)

n is an integer with n ≥ 1. You want body P to run exactly n times, with i equal to 0, 1, …, n − 1 at the start of each run. Which is correct?

1. i ← 0 / while i ≤ n / (body) P, i ← i + 1
2. i ← 0 / while i < n / (body) P, i ← i + 1
3. i ← 1 / while i < n / (body) P, i ← i + 1
4. i ← 0 / while i = n / (body) P, i ← i + 1

Answer: 2

• Option 1: runs for i = 0, 1, …, n, which is n + 1 times (one too many).
• Option 2: correct. The condition is true for i from 0 to n − 1 and becomes false at i = n, so it runs exactly n times. i increases by 1 each iteration, so n − i decreases and the loop always ends.
• Option 3: i takes 1, …, n − 1, so it runs n − 1 times, and the start value isn’t 0 (one too few).
• Option 4: puts the termination condition (i = n) where the continue condition belongs. At the start i = 0 ≠ n (n ≥ 1), so the condition is false and the body runs 0 times.

Question 3 (recursion return trace)

G(n):
    if n = 0
        return 0
    else
        return 2 * G(n − 1) + 1

When G(3) is called, which list gives the return values in the order the calls return?

1. 7, 3, 1, 0
2. 0, 1, 2, 3
3. 1, 3, 7, 15
4. 0, 1, 3, 7

Answer: 4

Call order: G(3) → G(2) → G(1) → G(0). Return order: G(0), G(1), G(2), G(3).

Return step	Call	Computation	Return value
1	G(0)	base case	0
2	G(1)	2×0 + 1	1
3	G(2)	2×1 + 1	3
4	G(3)	2×3 + 1	7

• Option 1: the values are right, but they are listed in call order (starting from G(3)). Returns happen deepest call first.
• Option 2: lists each call’s argument n in return order instead of the return values.
• Option 3: takes the base-case value as 1, which shifts every value by one step (if G(0) were 1, you would get 1, 3, 7, 15).
• Option 4: correct.

Question 4 (operation count, Big-O)

count ← 0
for i ← 1 to n
    count ← count + 1
for i ← 1 to n
    j ← 1
    while j < n
        count ← count + 1
        j ← 2 * j
output count

Counting convention: the number of executions of count ← count + 1 (= the output). Which pair gives the output for n = 8 and the time complexity when n is a power of 2?

1. 32, Θ(n log n)
2. 40, Θ(n log n)
3. 24, Θ(n log n)
4. 72, Θ(n²)

Answer: 1

• First loop: 8 executions.
• Second loop: for each i, the inner while runs for j = 1, 2, 4 (at j = 8, 8 < 8 is false), so 3 times = log₂ 8. 8 × 3 = 24 executions.
• Total 8 + 24 = 32. In general n + n·log₂ n, and the larger sequential block dominates, so Θ(n log n).
• Option 1: correct.
• Option 2 (40): an off-by-one error that reads the inner condition as j ≤ n and counts 4 per i (8 + 8×4).
• Option 3 (24): leaves out the first sequential block (8 executions).
• Option 4 (72, Θ(n²)): treats the inner loop as running n times (8 + 8×8). A doubling loop runs a logarithmic number of times.

Question 5 (state transition)

An automaton has the transition table below. The start state is R0.

Current state	Input 0	Input 1
R0	R0	R1
R1	R2	R0
R2	R1	R2

The input 1101 is read from the left, one symbol at a time. Which list gives the state immediately after reading each symbol, in order?

1. R1, R2, R2, R2
2. R0, R1, R0, R0
3. R1, R0, R0, R1
4. R1, R2, R2, R0

Answer: 3

k	Before	Input	After
1	R0	1	R1
2	R1	1	R0
3	R0	0	R0
4	R0	1	R1

• Option 1: reads the input from the right (1, 0, 1, 1): R0→R1→R2→R2→R2.
• Option 2: lists the state before reading each symbol, so the last symbol’s effect is lost.
• Option 3: correct. Final state R1. (Note: this table tracks the remainder mod 3 of a binary number read from the left. 1101₂ = 13, and 13 mod 3 = 1, which matches.)
• Option 4: guesses, without reading the table, that the machine counts 1s mod 3 (reading 1 in R1 goes to R0 in the table, but this option goes to R2).

---

10. Quick sheet

• ← is assignment, = is comparison. The question’s own symbol definitions always win.
• Trace table: initial row → define checkpoint → one statement at a time → keep old/new values separate → output and final state.
• while condition is a continue condition. The termination condition is its negation.
• Three loop checks: initialization, condition, update. A variant that strictly decreases and has a lower bound means the loop ends.
• Recursion: calls pile up on the way down and unwind in reverse. Progress toward the base case is required. Each call has its own variables.
• F(n) = n + F(n − 2): number of calls and stack depth Θ(n).
• 1 + 2 + … + n = n(n + 1)/2 → Θ(n²).
• Sequential blocks add, independent nesting multiplies, halving/doubling gives log.
• Exact count ≠ Θ (tight growth) ≠ O (upper bound) ≠ elapsed seconds.
• Finite-state machine: next state = f(current state, input). Check whether a row is “before reading” or “after reading”.

11. Common traps

1. Treating a value already updated in the same iteration as the old value (or the reverse).
2. Mixing up < and ≤, so the count is off by one.
3. Writing the termination condition directly after while.
4. Leaving out the update statement, causing an infinite loop.
5. Giving recursive returns in call order.
6. Misreading the base case’s return value so every value shifts.
7. Writing Θ/O with constant factors or lower-order terms left in (e.g., Θ(n²/2)).
8. Counting a doubling loop as n iterations.
9. Leaving recursion’s stack space out of the space complexity.
10. Confusing the reading direction or what moment a row represents in a state-transition trace.

12. Final self-check

• Without looking at Example 1, I can rebuild the four (x, total) rows and the output 15.
• I can compute 48 mod 18, 18 mod 12, and 12 mod 6, and explain the 3 iterations and the result 6.
• I can write F(5)’s call order and return order (return values 1, 4, 9) separately.
• I can show n(n + 1)/2 for the triangular nested loop, and 10 for n = 4, in a table.
• I can state in one sentence each how exact count, Θ, O, and auxiliary space differ.
• I can reproduce the parity automaton’s state sequence for 101101: E→O→O→E→O→O→E.
• I can explain why each wrong option in the five practice questions is wrong.

13. Review suggestion (1 / 3 / 7 days)

This is a general spaced-review suggestion, not a plan based on any learning data.

• After 1 day: read the quick sheet and rewrite the trace tables for Examples 1 and 2 on blank paper.
• After 3 days: redo Examples 3 and 4, then change to n = 5 and check by hand the triangular loop count (15) and F(7) (= 7 + 5 + 3 + 1 = 16).
• After 7 days: redo the five practice questions without the explanations, and for any you miss, find and mark the trap in Section 11.

---

14. Syllabus mapping

• 大分類1：基礎理論／中分類1：基礎理論／3. 情報に関する理論／（6）オートマトン
• 大分類1：基礎理論／中分類1：基礎理論／3. 情報に関する理論／（8）計算量
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（1）流れ図
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（2）代表的なアルゴリズム／②再帰のアルゴリズム
• 大分類1：基礎理論／中分類2：アルゴリズムとプログラミング／2. アルゴリズム／（3）アルゴリズム設計

15. Source

• IPA, “応用情報技術者試験（レベル3）シラバス Ver.7.2” https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kq5-att/syllabus_ap_ver7_2.pdf (Checked: 2026-10-20 / This article revised: 2026-10-20)
• The syllabus was used only to confirm exam scope. All explanations, examples, and practice questions in this article were written independently. No past exam questions or third-party explanations were used. This article is not approved or endorsed by IPA.