Answer to Question #278256 in C++ for zain

Question

Write the recursive functions for following

1.      find sum of an array

2.      Find largest number in array

3.      Given an array, check whether the array is in sorted order with recursion.

4.      Write a recursive bubble sort algorithm

5.      Write a recursive selection sort algorithm

6.      Recursion to find palindrome

7.      prints the numbers between 1 to n in a reverse order.

8.      Suppose that intArray is an array of integers, and length specifies the number of elements in intArray. Also, suppose that low and high are two integers such that 0 <= low < length, 0 <= high < length, and low < high. That is, low and high are two indices in intArray. Write a recursive definition that reverses the elements in intArray between low and high.

Answer 1

1.      find sum of an array

#include <iostream>
using namespace std; 
#define MAX_SIZE 100 
// declaring a function
int sum(int arr[], int start, int len);
int main()
{
    int array[MAX_SIZE];
    int num, i, sumOfArrayElements;
    // Inputtin size and elements in array
    cout<<"Enter array size: ";
    cin>>num;
    cout<<"Enter elements in the array: ";
    for(i=0; i<num; i++)
    {
        cin>>array[i];
    }
    sumOfArrayElements = sum(array, 0, num);
    cout<<"Sum of array elements: "<<sumOfArrayElements;
    return 0;
}
// Recursively finding the sum of elements in an array.
int sum(int array[], int start, int len)
{
    // Recursion base condition
    if(start >= len)
        return 0;
    return (array[start] + sum(array, start + 1, len));
}

2.      Find largest number in array

#include <iostream>
using std::cout;
using std::endl;
int maximumArr(int Array[], int size);
int main(){
  int myArray[] = { 1, 6, 8, 3 };
  int sizeOfArray = sizeof(myArray)/sizeof(*myArray);
  int largestNumber = maximumArr(myArray, sizeOfArray);
  cout<< "the largest number of the array is " << largestNumber << endl;
  return 0;
}
int maximumArr(int Array[], int size){
  if(size == 0){
    cout << "empty array" << endl;
  }
  if(size == 1 ){
    return Array[0];
  }else{
    return maximumArr(Array, size-1);
  }
}

3.      Given an array, check whether the array is in sorted order with recursion.

#include <bits/stdc++.h>
using namespace std;
int isArraySorted(int arr[], int n)
{
    if (n == 1 || n == 0)
        return 1;
    if (arr[n - 1] < arr[n - 2])
        return 0;
    return isArraySorted(arr, n - 1);
}
int main()
{
    int arr[] = { 20, 23, 23, 45, 78, 88 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isArraySorted(arr, n))
        cout << "Yes\n";
    else
        cout << "No\n";
}

4.      Write a recursive bubble sort algorithm

Bubble sort is one of the simplest sorting algorithms which sorts the elements by repeatedly swapping them if they are in the wrong order.

Recursive bubble sort Algorithm is as follows

//Recursive Bubble Sort
let recursiveBubbleSort = (arr, n = arr.length) => {
  //If there is only single element 
  //the return the array
  if(n == 1){
    return arr;
  }
  
  //Swap the elements by comparing them
  for(let j = 0; j < n - 1; j++){
    if(arr[j] > arr[j + 1]){
      [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
  
  //Recursively call the function to sort.
  return recursiveBubbleSort(arr, n-1);
}

5.      Write a recursive selection sort algorithm

The Selection Sort algorithm sorts maintains two parts. 

 

1. First part that is already sorted
2. Second part that is yet to be sorted.

The algorithm works by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the end of sorted part. 

Example

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64 

6.      Recursion to find palindrome

#include <bits/stdc++.h>
using namespace std;
int palindromeCheck(string s, int start, int end)
{
    if(end-start==1 || start==end)
    {
        return 1;
    }
    else
    {
        if(s[start]==s[end])
        {
            return palindromeCheck(s,start+1,end-1); 
        }
        else
        {
            return 0;
        }
    }
}
int main()
{
   string s;
   cin>>s;
   int n=s.length();
   if(palindromeCheck(s, 0, n-1))
   {
       cout<<"Yes"<<endl;
   }
   else
   {
       cout<<"No"<<endl;
   }
   return 0;
}

7.      prints the numbers between 1 to n in a reverse order.

#include<iostream>
using namespace std;
void rev(int num)
{
       if (num < 10)
       {
    cout<<num;
    return;
       }
       else
       {
           cout<<num % 10;


           rev(num/10);
       }
   }
int main()
{
    int num;
 cout<<"Enter your number :";
 cin>>num;
 cout<<"Reverse of the input number is:  ";
 rev(num);
}

8.      Suppose that intArray is an array of integers, and length specifies the number of elements in intArray. Also, suppose that low and high are two integers such that 0 <= low < length, 0 <= high < length, and low < high. That is, low and high are two indices in intArray. Write a recursive definition that reverses the elements in intArray between low and high.

#include <iostream>
using namespace std;
void rev(int array[], int n, int k)
{
    for (int i = 0; i < n; i += k)
    {
        int low = i;
        int high = min(i + k - 1, n - 1);
        while (low < high)
            swap(array[low++], array[high--]);
    }
}
int main()
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int k = 3;
 
    int n = sizeof(array) / sizeof(array[0]);
 
    rev(array, n, k);
 
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
 
    return 0;
}