Recursive Functions - Programming and Data Structures - Computer Science

In programming terms, a recursive function is a routine that calls itself directly or indirectly. Using recursive algorithms, certain problems can be solved quite easily. The Towers of Hanoi (TOH) is one classic programming exercise that demonstrates the power of recursion. It is worth noting that every recursive program can be written using iterative methods, though recursion often provides a more elegant and intuitive solution.

Mathematically, recursion helps solve many puzzles with remarkable simplicity. Consider this classic interview question: In a party of N people, each person shakes hands with every other person exactly once. In total, how many handshakes occur?

Example: Handshake Problem

Problem Statement: In a party of N people, each person shakes hands with every other person only once. In total, how many handshakes would happen?

Solution: This problem can be solved using various approaches including graphs and recursion. Let us examine the recursive approach.

Consider the N-th person. This person must shake hands with all (N-1) other persons. Once we account for the N-th person's handshakes, the problem reduces to finding the total handshakes among the remaining (N-1) persons.

Let \(T_N\) represent the total number of handshakes among N people. We can express this recursively as:

\[T_N = (N-1) + T_{N-1}\]

where the base case is \(T_1 = 0\) (a single person cannot shake hands with anyone).

Solving this recursive relation yields an arithmetic series that evaluates to:

\[T_N = \frac{N(N-1)}{2}\]

Exercise: In a party with N couples, assume every man shakes hands with every woman except his partner. How many handshakes occur?

Time Complexity of Recursive Algorithms

Recursive programs often result in poor time complexity. A classic example is the Fibonacci series. The time complexity of calculating the n-th Fibonacci number using simple recursion is approximately \(1.6^n\), meaning the computation time nearly doubles for each additional increment in n. This is because the recursive Fibonacci algorithm contains overlapping subproblems-the same values are computed multiple times.

Techniques such as dynamic programming and memoization can significantly improve the performance of algorithms with overlapping subproblems. However, several algorithms-such as merge sort and quick sort-achieve optimal time complexity using recursion because they divide problems into non-overlapping subproblems.

Base Case

One critical requirement of recursive functions is the termination point or base case. Every recursive program must have a base case to ensure that the function will terminate. Without a base case, recursive calls continue indefinitely until the program exhausts the call stack, resulting in a stack overflow.

Different Ways of Writing Recursive Functions

1. Direct Recursion: Function Calling Itself

In direct recursion, a function calls itself within its own definition. The Towers of Hanoi is a classic example of direct recursion. Below are implementations in multiple programming languages:

C++:

#include <bits/stdc++.h>
using namespace std;

// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole) {
  // Base case (termination condition)
  if (0 == n)
    return;
  
  // Move first n-1 disks from source pole to auxiliary pole
  // using destination as temporary pole
  tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
  
  // Move the remaining disk from source pole to destination pole
  cout << "Move the disk " << n << " from " << sourcePole
       << " to " << destinationPole << endl;
  
  // Move the n-1 disks from auxiliary (now source) pole to destination pole
  // using source pole as temporary (auxiliary) pole
  tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
}

// Driver code
int main() {
  tower(3, 'S', 'D', 'A');
  return 0;
}

C:

#include <stdio.h>

// Assuming n-th disk is bottom disk (count down)
void tower(int n, char sourcePole, char destinationPole, char auxiliaryPole) {
  // Base case (termination condition)
  if (0 == n)
    return;
  
  // Move first n-1 disks from source pole to auxiliary pole
  // using destination as temporary pole
  tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
  
  // Move the remaining disk from source pole to destination pole
  printf("Move the disk %d from %c to %c\n", n, sourcePole, destinationPole);
  
  // Move the n-1 disks from auxiliary (now source) pole to destination pole
  // using source pole as temporary (auxiliary) pole
  tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
}

int main() {
  tower(3, 'S', 'D', 'A');
  return 0;
}

Java:

class GFG {
  // Assuming n-th disk is bottom disk (count down)
  static void tower(int n, char sourcePole, char destinationPole,
                    char auxiliaryPole) {
    // Base case (termination condition)
    if (0 == n)
      return;
    
    // Move first n-1 disks from source pole to auxiliary pole
    // using destination as temporary pole
    tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
    
    // Move the remaining disk from source pole to destination pole
    System.out.printf("Move the disk %d from %c to %c\n", n, sourcePole,
                      destinationPole);
    
    // Move the n-1 disks from auxiliary (now source) pole to destination pole
    // using source pole as temporary (auxiliary) pole
    tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
  }

  public static void main(String[] args) {
    tower(3, 'S', 'D', 'A');
  }
}

Python3:

# Assuming n-th disk is bottom disk (count down)
def tower(n, sourcePole, destinationPole, auxiliaryPole):
  # Base case (termination condition)
  if n == 0:
    return
  
  # Move first n-1 disks from source pole to auxiliary pole
  # using destination as temporary pole
  tower(n - 1, sourcePole, auxiliaryPole, destinationPole)
  
  # Move the remaining disk from source pole to destination pole
  print(f"Move the disk {n} from {sourcePole} to {destinationPole}")
  
  # Move the n-1 disks from auxiliary (now source) pole to destination pole
  # using source pole as temporary (auxiliary) pole
  tower(n - 1, auxiliaryPole, destinationPole, sourcePole)

# Driver code
tower(3, 'S', 'D', 'A')

C#:

using System;

class GFG {
  static void tower(int n, char sourcePole, char destinationPole,
                    char auxiliaryPole) {
    // Base case (termination condition)
    if (0 == n)
      return;
    
    // Move first n-1 disks from source pole to auxiliary pole
    // using destination as temporary pole
    tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
    
    // Move the remaining disk from source pole to destination pole
    Console.WriteLine("Move the disk " + n + " from " + sourcePole + " to " +
                      destinationPole);
    
    // Move the n-1 disks from auxiliary (now source) pole to destination pole
    // using source pole as temporary (auxiliary) pole
    tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
  }

  // Driver code
  public static void Main() {
    tower(3, 'S', 'D', 'A');
  }
}

PHP:

<?php
// Assuming n-th disk is bottom disk (count down)
function tower($n, $sourcePole, $destinationPole, $auxiliaryPole) {
  // Base case (termination condition)
  if (0 == $n)
    return;
  
  // Move first n-1 disks from source pole to auxiliary pole
  // using destination as temporary pole
  tower($n - 1, $sourcePole, $auxiliaryPole, $destinationPole);
  
  // Move the remaining disk from source pole to destination pole
  echo "Move the disk ", $n, " from ", $sourcePole, " to ", $destinationPole,
       "\n";
  
  // Move the n-1 disks from auxiliary (now source) pole to destination pole
  // using source pole as temporary (auxiliary) pole
  tower($n - 1, $auxiliaryPole, $destinationPole, $sourcePole);
}

// Driver Code
tower(3, 'S', 'D', 'A');
?>

JavaScript:

<script>
// Assuming n-th disk is bottom disk (count down)
function tower(n, sourcePole, destinationPole, auxiliaryPole) {
  // Base case (termination condition)
  if (0 == n)
    return;
  
  // Move first n-1 disks from source pole to auxiliary pole
  // using destination as temporary pole
  tower(n - 1, sourcePole, auxiliaryPole, destinationPole);
  
  // Move the remaining disk from source pole to destination pole
  document.write("Move the disk " + n + " from " + sourcePole + " to " +
                 destinationPole + "<br>");
  
  // Move the n-1 disks from auxiliary (now source) pole to destination pole
  // using source pole as temporary (auxiliary) pole
  tower(n - 1, auxiliaryPole, destinationPole, sourcePole);
}

// Driver code
tower(3, 'S', 'D', 'A');
</script>

Output:

Move the disk 1 from S to D
Move the disk 2 from S to A
Move the disk 1 from D to A
Move the disk 3 from S to D
Move the disk 1 from A to S
Move the disk 2 from A to D
Move the disk 1 from S to D

Time Complexity Analysis of Towers of Hanoi

The time complexity of the Towers of Hanoi can be determined by analysing the number of disk moves required. Let \(M_N\) denote the total number of moves needed to transfer N disks.

To move N disks from the source pole to the destination pole, we must:

• Move the first (N-1) disks from source to auxiliary using destination as temporary
• Move the largest disk from source to destination
• Move the (N-1) disks from auxiliary to destination using source as temporary

This gives us the recurrence relation:

\[M_N = 2M_{N-1} + 1\]

where \(M_1 = 1\) (moving a single disk requires one move).

Solving this recurrence relation yields:

\[M_N = 2^N - 1\]

This is an exponential time complexity. For example, moving just 64 disks requires \(2^{64} - 1\) moves, which would take an extraordinarily long time even on modern computers.

2. Indirect Recursion: Mutual Function Calls

In indirect recursion, a function calls another function, which in turn calls the first function. Though rarely used in practice, this approach demonstrates the flexibility of recursion. When using indirect recursion, each function involved must have its own base case to ensure proper termination.

Defensive Programming with Call Depth Counter

Recursive programming is often avoided in safety-critical applications such as flight control systems or health monitoring devices. However, one defensive technique is to use a static call depth counter to prevent uncontrolled recursive calls. This approach may be used in soft real-time systems but should not be used in safety-critical applications.

C++:

void recursive(int data) {
  static int callDepth = 0;
  if (callDepth > MAX_DEPTH)
    return;
  
  // Increase call depth
  callDepth++;
  
  // do other processing
  recursive(data);
  
  // do other processing
  
  // Decrease call depth
  callDepth--;
}

C:

void recursive(int data) {
  static int callDepth = 0;
  if (callDepth > MAX_DEPTH)
    return;
  
  // Increase call depth
  callDepth++;
  
  // do other processing
  recursive(data);
  
  // do other processing
  
  // Decrease call depth
  callDepth--;
}

Java:

static int callDepth = 0;

static void recursive(int data) {
  if (callDepth > MAX_DEPTH)
    return;
  
  // Increase call depth
  callDepth++;
  
  // do other processing
  recursive(data);
  
  // do other processing
  
  // Decrease call depth
  callDepth--;
}

Python3:

callDepth = 0

def recursive(data):
  global callDepth
  if callDepth > MAX_DEPTH:
    return
  
  # Increase call depth
  callDepth += 1
  
  # do other processing
  recursive(data)
  
  # do other processing
  
  # Decrease call depth
  callDepth -= 1

C#:

static int callDepth = 0;

static void recursive(int data) {
  if (callDepth > MAX_DEPTH)
    return;
  
  // Increase call depth
  callDepth++;
  
  // do other processing
  recursive(data);
  
  // do other processing
  
  // Decrease call depth
  callDepth--;
}

JavaScript:

let callDepth = 0;

function recursive(data) {
  if (callDepth > MAX_DEPTH)
    return;
  
  // Increase call depth
  callDepth++;
  
  // do other processing
  recursive(data);
  
  // do other processing
  
  // Decrease call depth
  callDepth--;
}

The call depth depends on the function stack frame size and the maximum available stack size of the system. By maintaining a counter, the recursive function can monitor how deep the recursion has gone and terminate if it exceeds a predetermined limit, thereby preventing stack overflow errors.

3. Recursion Using Function Pointers

Recursion can also be implemented using function pointers. A notable example is signal handlers in POSIX-compliant systems. If a signal handler causes the same event that triggered the handler to occur again, the function will re-enter itself, creating an indirect recursive call through the function pointer mechanism. This form of recursion is particularly useful in event-driven programming and systems that require asynchronous callback mechanisms.