Home C++ Tutorial Program to check if an array is sorted or not using Recursion

Program to check if an array is sorted or not using Recursion

by Anup Maurya
20 minutes read

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";
}
C++

related posts

Leave a Comment

Enable Notifications OK No thanks