WZPDCL; Assistant Engineer (CSE)- 2019 Exam Taker: KUETপ্রশ্ন ও সমাধান

A recursive function is a function that calls itself, directly or indirectly, to solve a smaller instance of the same problem, until a base case is reached that stops further calls.

Two essential parts of any recursive function:

1. Base case: the simplest input, solved directly without further recursion (prevents infinite recursion).
2. Recursive case: breaks the problem into a smaller sub-problem and calls itself on that sub-problem.

Example — factorial (C):

int factorial(int n) {
    if (n == 0) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

Call stack for factorial(4):

graph TD
  A["factorial(4) = 4*factorial(3)"] --> B["factorial(3) = 3*factorial(2)"]
  B --> C["factorial(2) = 2*factorial(1)"]
  C --> D["factorial(1) = 1*factorial(0)"]
  D --> E["factorial(0) = 1 (base case)"]

Unwinding: 1 → 1×1=1 → 2×1=2 → 3×2=6 → 4×6=24.

Trade-offs: recursion often gives cleaner, more readable code for naturally hierarchical problems (tree traversal, Tower of Hanoi, divide-and-conquer algorithms like quicksort/merge sort), but each call consumes stack memory, so an unbounded/incorrect base case causes a stack overflow. Time complexity depends on how the recursion branches (e.g. O(n) for factorial, O(2ⁿ) for naive Fibonacci).

Exam takeaway: Every recursive function needs a base case that is actually reachable — without it, the recursion never terminates and the program crashes with a stack overflow.

A foreign key is one or more columns in a table that reference the primary key of another (or the same) table, establishing and enforcing a link between the two tables' data.

Example:

erDiagram
  DEPARTMENT ||--o{ EMPLOYEE : employs
  DEPARTMENT {
    int dept_id PK
    string dept_name
  }
  EMPLOYEE {
    int emp_id PK
    string name
    int dept_id FK
  }

Here, Employee.dept_id is a foreign key referencing Department.dept_id (the primary key of Department) — every employee's department value must exist in the Department table.

CREATE TABLE Employee (
  emp_id   INT PRIMARY KEY,
  name     VARCHAR(50),
  dept_id  INT,
  FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
);

When a foreign key is used:

• To model a real-world relationship between two entities (e.g. Employee belongs to a Department, Order belongs to a Customer).
• To enforce referential integrity — the database engine will reject an insert/update that references a non-existent parent row, and can cascade or restrict deletes on the parent.
• To support JOIN queries that combine related data across tables without duplicating it.

Exam takeaway: A foreign key must match a value already present as a primary (or unique) key in the referenced table — this is what "referential integrity" means, and it's the mechanism that prevents "orphan" rows in a relational database.