Is every recursive algorithm a divide and conquer algorithm?

Question

I have a problem for homework and I need to solve this problem with a divide and conquer algorithm.

I solved this algorithm by using recursion. Did I use divide and conquer automatically by using recursion?

For example, is this below approach a divide an conquer algorithm? Because I use fun function in fun.(recursive call)

Code:

    #include <stdio.h>

/* int a[] = {-6,60,-10,20}; */
int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};
int len = sizeof(a)/sizeof(*a);
int maxherearray[10];

int fun(int n);
int max(int a, int b);
int find_max(int a[], int len);
void print_array(int a[], int start_idx, int end_idx);

int start_idx = 0;  // Start of contiguous subarray giving max sum
int end_idx = 0;    // End of contiguous subarray giving max sum

#define NEG_INF (-100000)

int max_sum = NEG_INF;  // The max cont sum seen so far.

int main(void)
{
    start_idx = 0;
    end_idx = len - 1;
    maxherearray[0] = a[0];

    printf("Array a[]: ");
    print_array(a, 0, len-1);
    printf("\n");

    // Compute the necessary information to get max contiguous subarray
    fun(len - 1);
    printf("Max subarray value == %d\n", find_max(maxherearray, len));
    printf("\n");

    printf("Contiguous sums: ");
    print_array(maxherearray, 0, len - 1);
    printf("\n");

    printf("Contiguous subarray giving max sum: ");
    print_array(a, start_idx, end_idx);
    printf("\n\n");

    return 0;
}

int fun(int n)
{
    if(n==0)
        return a[0];

    int max_till_j = fun(n - 1);

    // Start of new contiguous sum
    if (a[n] > a[n] + max_till_j)
    {
        maxherearray[n] = a[n];

        if (maxherearray[n] > max_sum)
        {
            start_idx = end_idx = n;
            max_sum = maxherearray[n];
        }
    }
    // Add to current contiguous sum
    else
    {
        maxherearray[n] = a[n] + max_till_j;

        if (maxherearray[n] > max_sum)
        {
            end_idx = n;
            max_sum = maxherearray[n];
        }
    }

    return maxherearray[n];
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

// Print subarray a[i] to a[j], inclusive of end points.
void print_array(int a[], int i, int j)
{
    for (; i <= j; ++i) {
        printf("%d ", a[i]);
    }
}

int find_max(int a[], int len)
{
    int i;
    int max_val = NEG_INF;
    for (i = 0; i < len; ++i)
    {
        if (a[i] > max_val)
        {
            max_val = a[i];
        }
    }

    return max_val;
}

Answer 1

Every recursion function is not necessarily divide-and-conquer approach. There are other approaches like decrease-and-conquer(decrease by a constant factor, decrease by one, variable-size decrease).

Is this below approach a divide an conquer algorithm?

Your function is exactly decrease by a constant factor which is 1 approach. You can glance at here.

Pseudocode for the divide-and-conquer algorithm for finding a maximum-subarray

MaxSubarray(A,low,high)
//
if high == low   
   return (low, high, A[low]) // base case: only one element
else
   // divide and conquer
   mid = floor( (low + high)/2 )
   (leftlow,lefthigh,leftsum) = MaxSubarray(A,low,mid)
   (rightlow,righthigh,rightsum) = MaxSubarray(A,mid+1,high)
   (xlow,xhigh,xsum) = MaxXingSubarray(A,low,mid,high)
   // combine
   if leftsum >= rightsum and leftsum >= xsum
      return (leftlow,lefthigh,leftsum)
   else if rightsum >= leftsum and rightsum >= xsum
      return (rightlow,righthigh,rightsum)
   else
      return (xlow,xhigh,xsum)
   end if
end if

--------------------------------------------------------------

MaxXingSubarray(A,low,mid,high)
// Find a max-subarray of A[i..mid]
leftsum = -infty
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > leftsum
       leftsum = sum
       maxleft = i
    end if
end for
// Find a max-subarray of A[mid+1..j]
rightsum = -infty
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > rightsum
       rightsum = sum
       maxright = j
    end if
end for
// Return the indices i and j and the sum of the two subarrays
return (maxleft,maxright,leftsum + rightsum)

-----------------------------------------------------------

=== Remarks:

(1) Initial call: MaxSubarray(A,1,n)

(2) Divide by computing mid.
    Conquer by the two recursive alls to MaxSubarray.
    Combine by calling MaxXingSubarray and then determining
       which of the three results gives the maximum sum.

(3) Base case is when the subarray has only 1 element.

Answer 2

Not necessarily. If you explore the functional programming paradigm you will learn that the simple for loop can be replaced with recursion

for i in range(x):
    body(i)

changes to

def do_loop(x, _start=0):
    if _start < x:
         body(_start)
         do_loop(x, _start=_start+1)

and it's quite obvious that not every iteration is a divide and conquer algorithm.