569
In this program example, we’ll check if an array is sorted or not using Recursion.
Given an array of size n, write a program to check if it is sorted in ascending order or not. Equal values are allowed in an array and two consecutive equal values are considered sorted.
Input : 21 23 46 80 89 121 Output : Yes Input : 20 20 45 89 89 90 Output : Yes Input : 20 20 78 98 99 97 Output : No
Recursive approach
1: If size of array is zero or one, return true. 2: Check last two elements of array, if they are sorted, perform a recursive call with n-1 else, return false. If all the elements will be found sorted, n will eventually fall to one, satisfying Step 1.
Program to check if an array is sorted or not using Recursion
// Recursive approach to check if an
// Array is sorted or not
#include <bits/stdc++.h>
using namespace std;
// Function that returns 0 if a pair
// is found unsorted
bool arraySortedOrNot(int arr[], int n)
{
// Array has one or no element or the
// rest are already checked and approved.
if (n == 1 || n == 0)
return true;
// Unsorted pair found (Equal values allowed)
if (arr[0] > arr[1])
return false;
// Last pair was sorted
// Keep on checking
return arraySortedOrNot(arr, n - 1);
}
// Driver code
int main()
{
int arr[] = { 20, 23, 23, 45, 78, 88 };
int n = sizeof(arr) / sizeof(arr[0]);
if (arraySortedOrNot(arr, n))
cout << "Array is sorted\n";
else
cout << "Array is not sorted\n";
}
