Quartz 4

2.4 Recursion

2 min read

Index

  1. What is Recursion?
  2. How to Think Recursively
  3. Recursion Structure (C++ Skeleton)
  4. Types of Recursion
  5. Example
    1. Reverse of an Array using Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller subproblems of the original problem.

A recursive function must have:

  • Base Case(s): Condition to stop recursion.
  • Recursive Case(s): Function calls itself with smaller input.

How to Think Recursively

  1. Identify the subproblem: Can the problem be broken into smaller identical subproblems?
  2. Define base case(s): When should the recursion stop?
  3. Ensure progress: Each recursive call should move toward a base case.
  4. Combine results (if needed): Useful in divide & conquer.

Recursion Structure (C++ Skeleton)

void func(parameters) {
    // Base case
    if (base_condition) return;
 
    // Recursive case
    func(smaller_problem);
}

Types of Recursion

  1. Tail Recursion: The recursive call is the last operation.
void func(parameters) {
    // Base case
    if (base_condition) return;
	//actions 
	----- 
	-----
    // Recursive case
    func(smaller_problem);
}
  1. Head Recursion: The recursive call is the first operations.
void func(parameters) {
    // Base case
    if (base_condition) return;
    // Recursive case
    func(smaller_problem);
	//actions 
	----- 
	-----
}
  1. Tree Recursion: Multiple recursive call at each level.
void func(parameters) {
    // Base case
    if (base_condition) return;
    // Recursive case
    func(smaller_problem);
	//actions 
	----- 
	-----
	func(smaller_problem);
}
  1. Indirect Recursion: Function A calls Function B, Function B then calls Function A for a reduced value. A → B → C
void funcA(parameters){
	// Base Case
	if (base_condition) return;
	// Function Call 
	funcB(<reduced_parameters>); 
}
 
void funcB(parameters){
	// Base Case
	if (base_condition) return;
	funcA(<reduced_parameters>);
}

Example

Reverse of an Array using Recursion

#include <bits/stdc++.h>
#include <iostream>
 
const int MAXN = 1e5 + 5;
int reverse_array[MAXN];
 
void reverse(int *x, int s, int n) {
  if (s == n) { //base case
    return;
  }
  reverse(x, s + 1, n); //recursive case
  reverse_array[s] = x[n - s - 1];
}
 
int main() {
  int arr[10] = {42, 7, 13, 89, 23, 56, 17, 3, 91, 64};
 
  reverse(arr, 0, sizeof(arr) / sizeof(arr[0]));
  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
    std::cout << reverse_array[i] << " ";
  }
  std::cout << '\n';
  return 0;
}

Graph View