6.RevArray.md

📘 Printing an Array in Reverse Order Using Recursion

🧾 Problem Statement

Goal: Given an array of n elements, write a recursive function to print its contents in reverse order (from the last element to the first), each on its own line or separated by spaces.

---

📦 Code

#include <iostream>
using namespace std;

// Recursive function to print arr[0..n-1] in reverse
void printReverse(int arr[], int n) {
    // Base case: no elements left
    if (n <= 0) {
        return;
    }
    // Print the last element
    cout << arr[n - 1] << ' ';
    // Recurse to print the remaining (0..n-2)
    printReverse(arr, n - 1);
}

int main() {
    int n;
    cin >> n;                      // Read number of elements
    int* arr = new int[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];             // Read array values
    }

    printReverse(arr, n);          // Print in reverse
    cout << endl;

    delete[] arr;
    return 0;
}

---

🧠 Key Concepts

✅ Recursion

• Definition: A function calls itself to handle a smaller subproblem.

• Essential Parts:

  1. Base Case: Terminates recursion (here, when n ≤ 0).
  2. Recursive Call: Reduces the problem size (n - 1).

✅ Head vs. Tail Recursion

• In this implementation, the print happens before the recursive call, making it a head-recursive pattern for reversing order.

---

🧮 Dry Run Example

Let’s take arr = [10, 20, 30], n = 3:

Call	Action	Output So Far
printReverse(arr, 3)	prints arr[2] = 30	30
	calls printReverse(arr, 2)
printReverse(arr, 2)	prints arr[1] = 20	30 20
	calls printReverse(arr, 1)
printReverse(arr, 1)	prints arr[0] = 10	30 20 10
	calls printReverse(arr, 0)
printReverse(arr, 0)	base case → return	30 20 10

Final Output:

30 20 10 

---

🔁 Algorithm

FUNCTION printReverse(arr, n):
    IF n ≤ 0:
        RETURN                  // Base case

    PRINT arr[n-1]              // Output the last element
    printReverse(arr, n-1)      // Recurse on the first n-1 elements

---

📌 Step-by-Step Approach

1. Read Input

   • Integer n (array size).
   • Array arr[] of length n.

2. Base Case

   if (n <= 0) return;

   • Stops recursion when no elements remain.

3. Print Current Element

   cout << arr[n - 1] << ' ';

   • Prints the element at index n-1.

4. Recursive Call

   printReverse(arr, n - 1);

   • Continues reversing the order for n-1 elements.

---

💻 Sample Input & Output

Input:

5
3 1 4 1 5

Output:

5 1 4 1 3 

---

📈 Complexity Analysis

Metric	Value
🕒 Time Complexity	O(n)
🧠 Space Complexity	O(n) (call stack)

• Time: Each element leads to one function call.
• Space: Maximum recursion depth = n.

---

📎 Notes & Enhancements

• Alternate Approach (Tail Recursion): You can use an index parameter to make it tail-recursive:

  void printReverse(int arr[], int idx, int n) {
      if (idx == n) return;
      printReverse(arr, idx + 1, n);
      cout << arr[idx] << ' ';
  }
  // Call with printReverse(arr, 0, n);

• Iterative Alternative:

  for (int i = n - 1; i >= 0; --i)
      cout << arr[i] << ' ';

• Memory Management:

  • Demonstrated new[]/delete[] for dynamic arrays; you may use std::vector<int> in modern C++.

---