Chapter 2 — Functions And Recursion

What is a function? A function is a named, self-contained block of code that performs a specific task and optionally returns a value. In mathematics, a function f maps each element of a domain to exactly one element of a codomain: f: A → B. In programming, a function (also called procedure/method) has a signature (name, parameter list, return type) and a body.

Parts of a programming function — name, parameters (formal arguments), return type/value, body (statements), and optional parameter/default values. Example signature: int sum(int a, int b) { return a + b; }.

Calling and parameter passing — when a function is called, actual parameters (arguments) are supplied. Parameters can be passed by value (a copy) or by reference (alias). Scope rules determine visibility of variables (local vs global).

Why use functions? Modularity, reusability, easier testing and debugging, abstraction (hide implementation), and clearer code structure.

Recursive functions — a function that calls itself to solve a smaller instance of the same problem. A correct recursive function must have:

• Base case(s) — one or more stopping conditions that return directly without recursion.
• Recursive case — reduces the problem toward the base case.

Example recursion ideas: factorial, Fibonacci, binary search, tree traversals. Recursion uses the call stack: each call creates a new activation record (local variables, return address). Excessive recursion depth can cause stack overflow; some recursive problems are better solved iteratively for efficiency.

Complexity and recurrence — many recursive algorithms satisfy recurrence relations (e.g., T(n) = T(n-1) + O(1) for linear recursion). Solving these recurrences gives time complexity (e.g., factorial recursion O(n), naive recursive Fibonacci O(φ^n)).

Common mistakes — missing/incorrect base case, not reducing the problem on each call, modifying shared mutable state unexpectedly, expensive repeated work in naive recursion (use memoization/DP).

Good practices — keep functions short and single-purpose, use clear parameter names, document preconditions/postconditions, prefer iterative solutions when recursion depth or repeated work is problematic, and use memoization to optimize overlapping subproblems.

Short pseudo-code examples:

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

// sum of first n numbers (function)
int sumN(int n) {
  return n * (n + 1) / 2;  // direct formula inside a function
}

What is a function? A function is a named block of code that performs a specific task, optionally accepts input values (parameters), and optionally returns a value. Functions promote modularity, reuse and abstraction.

Components of a function: name, parameter list (formal parameters), body (statements), return type/value (optional) and, in some languages, a declaration/prototype.

Definition vs Declaration: A definition provides the body (actual implementation). A declaration (or prototype) announces the function signature so the compiler/ interpreter knows how to call it. In some languages (Python) declaration and definition are combined.

Calling a function: To use a function you call it from another part of the program by writing its name and supplying arguments (actual parameters). Control transfers to the function body; when execution finishes (or a return is executed) control returns to the caller, optionally with a return value.

Parameter passing:

• Call by value: the function receives copies of arguments — changes inside do not affect caller variables.
• Call by reference (or by pointer): the function receives references so changes affect the original variables.

Scope and lifetime: Local variables declared inside a function are accessible only within that function (local scope) and exist while the function is active. Global variables are accessible across functions (global scope) but should be used sparingly.

Return statement: Used to send a value back to the caller. A function that does not return a value is often called a procedure (void in C/C++/Java).

Advantages: code reuse, easier debugging, readability, divide-and-conquer design, easier testing.

Functions and recursion: A function may call itself (recursion). Recursive solutions must have one or more base cases to stop recursion and one or more recursive cases that reduce the problem size. Each recursive call creates a new activation record on the call stack.

Common pitfalls: forgetting base case (infinite recursion), incorrect parameter passing (unexpected side effects), stack overflow for deep recursion, mismatched return types/signature.

Practical note: Choose between iterative and recursive approaches based on clarity, performance and stack usage. Tail recursion can be optimized by some compilers/ interpreters.

What is a function? A function (or procedure/method) is a named block of code that performs a specific task, can take inputs (parameters) and can optionally return a result. Functions help modularize code, improve readability and enable reuse.

Classification of functions

• By parameters and return value (the most commonly taught classification in Class 12):
  • Type 1 – No parameters, no return value
    Used when the function performs a task that needs no input and returns nothing (e.g., print a fixed message).
  • Type 2 – Parameters, no return value
    Takes inputs and performs some action (e.g., display a formatted report) but does not return a value to the caller.
  • Type 3 – No parameters, returns a value
    Uses internal data or global state to compute and return a value (less common; e.g., generate and return a random number).
  • Type 4 – Parameters and return value
    Accepts inputs and returns a computed result (e.g., add two numbers and return the sum).
• By origin:
  • Built-in / Library functions — provided by the programming language or libraries (e.g., print(), sqrt()).
  • User-defined functions — written by the programmer to perform specific tasks in the program.
• By behavior:
  • Recursive functions — a function that calls itself directly or indirectly to solve a problem by breaking it into smaller subproblems. Every recursive function needs a base case to stop recursion.
  • Non-recursive (iterative) functions — use loops or other constructs instead of self-calls.
  • Pure functions — same inputs always produce same outputs and have no side effects (useful in functional programming).
  • Impure functions — depend on or modify external state (I/O, global variables).

Types of recursion (important in Chapter: Functions & Recursion):

• Direct recursion — function calls itself (e.g., factorial).
• Indirect recursion — function A calls B and B calls A.
• Tail recursion — recursive call is the last operation; can be optimized by some compilers/interpreters into iteration.
• Non-tail (general) recursion — has additional work after the recursive call (e.g., building up results), e.g., recursion used in Fibonacci naive form.
• Linear recursion — each call makes at most one recursive call.
• Tree recursion — calls multiple recursive instances (e.g., naive Fibonacci), creating a branching tree of calls.

Key ideas when using functions and recursion:

• Always identify inputs (parameters), outputs (return value) and side effects.
• For recursion, clearly define a base case (stopping condition) and a recursive case (how the problem is reduced).
• Consider time and space costs: recursion uses call stack memory proportional to recursion depth.

Definitions: A parameter (formal parameter) is a variable listed in a function's definition. An argument (actual parameter) is the real value passed to the function when it is called. Example: in def add(x, y): x and y are parameters; in add(2, 3), 2 and 3 are arguments.

Kinds of parameters / arguments:

• Positional (positional-only): Values are matched by order (e.g., f(a, b)).
• Keyword (named): Values passed with parameter names (e.g., f(b=2, a=1)); order not required.
• Default parameters: Parameters given default values in the definition; callers may omit them.
• Variable-length (varargs): Functions that accept an arbitrary number of arguments (e.g., *args, **kwargs in Python; variadic functions in other languages).
• Function-as-argument (higher-order): A function can accept another function as an argument (used in callbacks, map/filter).

Parameter passing mechanisms:

• Pass-by-value: A copy of the value is passed; changes inside the function do not affect caller variables (common in C for primitive types).
• Pass-by-reference: A reference (alias) is passed; changes in the function affect the caller's variable (used in C++ with references, or when passing mutable objects in some languages).
• Language-specific model: Many modern languages use a hybrid model (e.g., Python: names bound to objects; mutable objects can be changed via a parameter, immutable cannot be re-bound by the function to change the caller's object).

Why parameters matter in recursion: Each recursive call creates a new set of parameters (a new stack frame). Parameters carry the current state; correctly updating parameters and ensuring a base case are essential to avoid infinite recursion or stack overflow.

Best practices: keep parameter lists short and meaningful, use default/keyword arguments for clarity, avoid side-effects unless intended (document when functions modify passed objects), and validate arguments early (type/range checks).

What is a return statement? A return statement ends a function’s execution and optionally sends a value (or values) back to the caller. The caller can then use that value in expressions, assignments or further processing. In many languages a function with no explicit return returns a default (for example None in Python).

Behavior and flow: When a return executes, control immediately goes back to the caller — code after that return in the function is not executed. A function may contain several return statements (multiple returns) placed in different branches (for example inside if blocks) to produce different outcomes depending on input or conditions.

Multiple returns — two meanings:

• Multiple return statements: more than one return appears in the function body; only one executes per call, determined by runtime path. This is common for early exits, error checks, or cases handling.
• Returning multiple values: a function may return a compound value (tuple, list, object) so the caller receives several pieces of data at once. Languages differ: Python supports returning multiple values naturally as a tuple, while languages like Java/C++ return a single value but you can return an array or an object to carry multiple results.

Return in recursion: In recursive functions the return propagates values up the call stack. Each recursive call returns a value computed from smaller subproblems; the caller uses that returned value to compute its own result. Correct base-case return is essential to stop recursion and start unwinding.

Differences between print and return: print only displays data to the console; return gives data to the caller for further use. Tests and composition of functions require return, not print.

Definition: Scope of a variable is the region of the program source code where the name of the variable is visible and can be used. Lifetime (or storage duration) is the time period during program execution when the variable exists in memory and retains a value.

Kinds of Scope:

• Block (local) scope: Visible only inside the block or function where it is declared. Example: variables declared inside { } or inside a function.
• Function scope: Name is visible throughout the function (common for labels or C-style identifiers inside a function).
• File (internal) scope: Visible to all functions in the same source file (in C/C++ this can be created with the static keyword at file level).
• Global (external) scope: Visible across the entire program (other files can access with extern in C/C++).
• Class/instance scope: In OOP, member variables have scope tied to class or instance and access controlled by access specifiers.
• Lexical (static) scope: Most modern languages use lexical scoping where nested blocks determine visibility; inner blocks can access outer variables.

Kinds of Lifetime / Storage Duration:

• Automatic (local) lifetime: Created on entry to the block or function (usually allocated on the stack) and destroyed when the block/function exits. Each call to a function gets a fresh set of these variables. This is the default for local variables in C/C++ and many languages.
• Static lifetime: Allocated once and exist for the entire program run. Examples: global variables and variables declared static at function or file scope in C/C++.
• Dynamic lifetime: Created and destroyed explicitly at runtime (allocated on the heap using malloc/new or language-specific allocators). Lifetime is controlled by programmer or garbage collector.

Important interactions:

• Two different variables can have the same name if their scopes do not overlap (shadowing). The inner declaration hides the outer one while inside the inner scope.
• In recursion, automatic variables are distinct per activation (each call has its own copy on the stack), while static variables are shared across calls.
• Access modifiers and keywords: in C/C++ keywords like static, extern, register modify linkage or storage class; in Python keywords like global and nonlocal affect name binding in nested scopes.

Small code examples:

// C++: scope and lifetime
int global_x = 10;   // global: file/external scope, static lifetime

void f() {
    int local_y = 5; // local: block scope, automatic lifetime
    static int s = 0; // static local: block scope, static lifetime
    s++;
}

// Recursion: each call gets its own automatic variables
int fact(int n) {
    int result = 1; // result is recreated each call
    if (n <= 1) return 1;
    return n * fact(n-1);
}

Practical notes:

• Prefer small scope: declare variables as near as possible to their use to avoid bugs from unintended access or modification.
• Use static/global sparingly: they persist for entire run and can cause hidden dependencies and harder-to-find bugs.
• Understand memory model: automatic -> stack, static/global -> data segment, dynamic -> heap. This affects lifetime, performance, and concurrency behavior.

What is a recursive function?
A recursive function is a function that calls itself directly or indirectly to solve a problem by breaking it into smaller subproblems. Each recursive call works on a smaller or simpler input until a base case is reached, which returns a result without any further recursion.

Key components

• Base case: Condition under which the function returns a result immediately (terminates recursion).
• Recursive case: Part where the function calls itself with a smaller/simpler argument.
• Call stack / activation records: Each call is placed on the program stack storing local variables and return address. When a base case returns, calls are popped in reverse order.

Important properties and rules

• Every recursive function must have at least one base case that is reachable; otherwise it leads to infinite recursion (stack overflow).
• Recursion divides the original problem into one or more subproblems of the same kind.
• Types: direct recursion (function calls itself) and indirect recursion (A calls B and B calls A).
• Tail recursion: the recursive call is the last operation in the function. Some compilers/interpreters can optimize tail recursion to reuse stack frames.
• Recursion is useful for problems with natural self-similar structure: tree traversals, factorial, Fibonacci, divide-and-conquer algorithms.

Advantages and disadvantages

• Advantages: Cleaner and simpler code for many problems (trees, graphs, divide-and-conquer); mirrors mathematical definitions.
• Disadvantages: Extra memory overhead for the call stack; may be inefficient (e.g., naive Fibonacci); sometimes harder to reason about space/time than iterative solutions.

Simple examples (Python-style pseudocode)

# Factorial (linear recursion)
def fact(n):
    if n == 0:
        return 1        # base case
    return n * fact(n-1)  # recursive case

# Binary search (divide and conquer)
def binary_search(arr, low, high, key):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == key:
        return mid
    elif arr[mid] > key:
        return binary_search(arr, low, mid-1, key)
    else:
        return binary_search(arr, mid+1, high, key)

Performance intuition
Recurrence relations express the running time of recursive algorithms. Solving these recurrences gives time complexity (examples below).

When to convert recursion to iteration
If recursion causes large stack usage or duplicated work (e.g., naive Fibonacci), you can convert to loops or use memoization/dynamic programming to improve efficiency.

Debugging tips
Trace calls on paper or draw the call stack. Ensure each recursive call progresses toward the base case.

What tracing a recursive call means
Tracing a recursive function means simulating its execution manually (or with a debugger) to record the sequence of calls, the values of parameters in each call, the order in which calls return, and how results combine. Tracing highlights the call stack (activation records), base case hits, and the flow of control between recursive calls.

Why tracing is important
It helps you verify correctness, find missing/incorrect base cases, understand time and space costs, and spot opportunities for optimization (tail recursion, memoization, converting to iteration).

Key elements when tracing

• Identify the base case(s) and the recursive case(s).
• Record the parameter values on each call and the return value when the call finishes.
• Draw the call stack (top = current call) or the call tree (each node = one call) to visualize order and concurrency of subcalls.
• Count calls to estimate time cost and note maximum stack depth to estimate space cost.

How to trace (step-by-step)

1. Start from the initial call: write its parameters.
2. If it meets a base case, write the return value and pop it from the stack.
3. If not, expand it into the recursive call(s): push the first subcall and repeat.
4. When a subcall returns, use its return value(s) to compute the parent’s return, then pop the parent when done.
5. Repeat until the initial call returns.

Analyzing complexity from traces
Use the pattern of calls you saw to write a recurrence for time T(n). Solve the recurrence or apply the Master Theorem for divide-and-conquer recurrences. Space complexity is typically proportional to the maximum recursion depth (plus any additional per-call local space).

Common patterns

• Linear recursion (one subcall per call): T(n) = T(n-1) + O(1) → O(n). Example: factorial, linear list processing.
• Binary/branching recursion (two or more subcalls): T(n) = T(n-1) + T(n-2) + O(1) or similar → often exponential (e.g., naive Fibonacci).
• Divide-and-conquer (a subproblems each of size n/b): T(n) = a T(n/b) + f(n) → use Master Theorem (e.g., merge sort).
• Tail recursion: recursive call is the last action. Can be converted to iteration or optimized by some compilers to O(1) extra space.

Practical tips

• Always verify base cases first — missing or incorrect base cases cause infinite recursion (stack overflow).
• When multiple subcalls repeat computation, consider memoization or dynamic programming to avoid exponential blow-up.
• Use a debugger or draw call trees for medium-sized inputs to see patterns; derive general recurrence from the observed pattern.

What is recursion? Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. Every correct recursive function has:

• Base case(s): one or more conditions that stop further recursion (prevent infinite calls).
• Recursive case(s): one or more self-calls that move the problem toward the base case.

Key concepts:

• Call stack / stack frames: each recursive call uses a new stack frame holding parameters and local variables. Depth equals the maximum number of simultaneous calls.
• Progress toward base case: recursive calls must reduce problem size (e.g., n → n-1 or n → n/2).
• Types of recursion: linear (single recursive call per activation), binary/multi-branch (multiple recursive calls, e.g., Fibonacci), and tail recursion (recursive call is the function's last action).
• Divide and conquer: algorithms split the input into subproblems, solve them recursively, then combine results (e.g., merge sort, quick sort).

Why use recursion? It gives clear, concise solutions to problems that are naturally self-similar: tree traversals, combinatorial generation (permutations, subsets), mathematical definitions (factorial, Fibonacci), and divide-and-conquer algorithms.

Practical pointers: ensure base case correctness, check that each recursive call makes progress, beware of exponential time when calls branch heavily (use memoization or convert to iterative if necessary), and be mindful of recursion depth (stack overflow).

Overview

Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. Iteration uses loops (for/while) to repeat steps. Converting recursion to iteration means replacing self-calls with loops and, if needed, an explicit stack or accumulator variables so the algorithm produces the same output without using the language call stack.

Why convert?

• Recursion is often simpler and clearer for divide-and-conquer, tree/graph traversal, and backtracking problems.
• Iteration is usually more memory-efficient (no call stack overhead) and sometimes faster in practice — important when n is large or recursion depth is limited.

General conversion methods

1. Tail recursion → Loop: If the last action of a function is a recursive call (tail recursion) you can replace the call with an update of parameters inside a loop and use an accumulator to carry results. Many compilers/languages can optimize tail calls, but some (e.g. Java, Python) do not, so manual conversion may be needed.
2. Non-tail recursion → Explicit stack: For general recursion (e.g. tree traversals, DFS) simulate the call stack with your own stack data structure and loop while the stack is not empty. Push state frames (parameters/local variables) onto the stack to emulate recursive behavior.
3. Memoization → Iterative DP: If recursion recomputes overlapping subproblems (e.g. naive Fibonacci), convert to bottom-up dynamic programming (iteration) to compute and store results once.

Steps to convert a recursive function to iterative

1. Identify the state: parameters and local variables needed for each call.
2. For tail recursion: convert into a loop by updating state variables and using an accumulator for the result.
3. For non-tail recursion: create a stack of frames. Each frame contains the same state a recursive call would have. Use loop + push/pop to process frames in the correct order.
4. Ensure you reproduce the base case behavior with conditional checks in the loop or when pushing frames.

Complexity considerations

• Time complexity often remains the same when converting recursion to iteration (you still perform the same operations), but constant factors may improve.
• Space complexity: recursion uses extra space on the call stack equal to recursion depth. Iteration with an explicit stack still uses space but gives control over storage and may allow constant-space solutions (e.g. tail recursion → O(1) space).

When to use which

• Use recursion when it makes code clearer and when problem structure is naturally recursive: tree algorithms, divide-and-conquer (merge sort, quicksort), backtracking (permutations, N-queens).
• Use iteration when you need better memory efficiency, when recursion depth might overflow the call stack, or when performance / tight resource constraints matter.
• If recursion causes excessive repeated work, prefer iterative dynamic programming or add memoization; sometimes an iterative DP is clearer and faster.

Small examples (explanatory)

1) Factorial (tail-call-friendly):

Recursive (tail):
int fact(int n, int acc) {
  if (n == 0) return acc;
  return fact(n-1, acc * n);
}

Iterative:
int factIter(int n) {
  int acc = 1;
  while (n > 0) {
    acc *= n;
    n--;
  }
  return acc;
}

2) Fibonacci — naive recursion vs iteration / DP:

Naive recursion:
int fib(int n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2); // exponential time
}

Iterative DP (bottom-up):
int fibIter(int n) {
  if (n <= 1) return n;
  int a = 0, b = 1;
  for (int i = 2; i <= n; ++i) {
    int c = a + b;
    a = b; b = c;
  }
  return b;
}

3) Binary tree inorder traversal — recursion vs explicit stack:

Recursive:
void inorder(Node root) {
  if (root == null) return;
  inorder(root.left);
  visit(root);
  inorder(root.right);
}

Iterative with stack:
void inorderIter(Node root) {
  Stack st = new Stack<>();
  Node cur = root;
  while (cur != null || !st.isEmpty()) {
    while (cur != null) { st.push(cur); cur = cur.left; }
    cur = st.pop();
    visit(cur);
    cur = cur.right;
  }
}

Practical notes for Class 12 students

• Understand how the call stack grows and why recursion can cause stack overflow.
• Practice converting simple tail-recursive functions to loops first, then try non-tail examples using an explicit stack.
• Recognize patterns: tree → stack; divide-and-conquer → recursion unless resource limits force iteration.

Overview: Functions and recursion are fundamental tools for decomposition and repeated computation. Good practices make recursive programs correct, readable and efficient; common errors cause wrong results, infinite loops, or runtime crashes (stack overflow).

Good practices:

• Define a clear base case: Always identify and test the stopping condition(s). The base case must be reachable and correct.
• Ensure progress toward the base case: Each recursive call must operate on a strictly smaller/simpler input so recursion terminates (e.g., n-1, n/2, smaller subarray length).
• Keep functions short and single-purpose: One responsibility per function improves readability and testing.
• Use meaningful names and parameter lists: Name parameters to reflect their role (e.g., index, n, start, end) and avoid many hidden/global dependencies.
• Avoid unnecessary work: Cache or memoize repeated subproblems (e.g., Fibonacci) or convert to iterative when recursion causes repeated recomputation.
• Prefer tail recursion (when available): Tail-recursive functions can be optimized into loops by some compilers/interpreters, reducing stack use. If not available, convert to an iterative approach.
• Document preconditions and side-effects: State whether a function modifies its inputs, uses globals, or relies on invariants.
• Test small and edge inputs: Test base cases, very small inputs (0,1), largest expected inputs, and invalid inputs to ensure robustness.

Common errors:

• Missing or incorrect base case: Leads to infinite recursion and stack overflow.
• Wrong progress step: Recursing without reducing the problem correctly (for example, using n+1 instead of n-1 or wrong index update) prevents termination.
• Off-by-one errors: Incorrect bounds for indices (start/end) cause missing elements or infinite recursion when indexes never converge.
• Excessive recomputation: Naive recursive solutions (e.g., naive Fibonacci) repeat subproblems exponentially; use memoization or dynamic programming.
• Modifying shared/mutable state: Changing global variables or mutable arguments inside recursion can produce hard-to-find bugs.
• Stack overflow due to deep recursion: Using recursion for very deep problems can exceed the call stack; convert to iterative or use tail recursion optimization if supported.
• Wrong return values: Forgetting to return the recursive result or combining results improperly (e.g., summing wrong subresults) yields incorrect outputs.
• Language-specific pitfalls: Examples: default mutable arguments in Python, forgetting const correctness in C++, or not handling pass-by-reference vs pass-by-value as intended.

Checklist before finalizing a recursive function:

1. Is there a clear base case and does it return the correct value?
2. Does each recursive call move input closer to the base case?
3. Are you avoiding repeated work (use memoization if needed)?
4. Does the function have a single, well-documented purpose and no unexpected side-effects?
5. Have you tested edge cases (0, 1, empty arrays) and large inputs?

Short example (pseudo-code):

// Correct factorial
function fact(n):
  if n == 0:           // base case
    return 1
  else:
    return n * fact(n-1)  // progress: n decreases

Incorrect variant (common error):

// Missing base case or wrong step — will not terminate
function badFact(n):
  return n * badFact(n)  // never reduces n -> infinite recursion