Recursion in C - Largest element of an array

Question

This program uses the recursion method to return the largest element of an array:

#include <stdio.h>

int maiorVetor(int *V, int N) {
    int maior;
    if (N == 1)
        return V[0];
    else {
        maior = maiorVetor(V, N - 1);
        if (maior > V[N - 1])
            return maior;
        else
            return V[N - 1];
    }
}

int main () {
    int A[10] = { 12, 65, 14, 38, 33, 11, 20, 23, 21, 43 };

    printf("%d", maiorVetor(A, 10));
    return 0;
}

Can someone please explain me step by step how this program works? Because in my head it seems like that when the program reaches maior = maiorVetor(V, N-1); it won't continue but just restart until the N = 0. But in fact the program works and it really gives me a true solution. I am confused how can this recursion work.

What do you think happens when it gets to `maior = maiorVetor(V, N-1)`? It calls `maiorVetor`, right? When `maiorVetor` returns, what happens? It goes to the next line, right? `if(maior > V[N-1])` — user253751, Mar 17 '20 at 15:06
Use just an array of 3 ints that could be relatively easily worked out on paper or in head. Use a debugger to step through the code and see what happen. — Eraklon, Mar 17 '20 at 15:07
One can explain how the program works after you understand how the program works. A slight paraphrase of the more common "to understand recursion, you must first understand recursion." — William Pursell, Mar 17 '20 at 15:13
But when maiorVetor returns the array is just V[0] because it has decremented N multiple times right? And when it goes to the next line, the array has N=0 or don't? — Henrique Jesus, Mar 17 '20 at 15:17
@HenriqueJesus it's not the same `N`. In every invocation of `maiorVetor` you have a different `N`. Run it step by step with your debugger with a simple case (e.g.) just 3 elements in the `A`. That's also a great opportunity to learn how to use your debugger. — Jabberwocky, Mar 17 '20 at 15:25
Otherwise for learning the basics of recursion just google ""factorial recursion explained". — Jabberwocky, Mar 17 '20 at 15:27
There is a simple example [here](https://stackoverflow.com/a/23137820/645128) explaining recursion, and how to implement it. — ryyker, Mar 17 '20 at 15:58

Kritin · Accepted Answer · 2020-03-17T21:25:44.813

I WILL DRAW A RECURSION TREE AND THEN TRY TO EXPLAIN IT

I am modifying & reducing the size of the array in your program to make it easier to explain -

#include <stdio.h>
int maiorVetor(int A, int N) {
    int maior;
    if(N == 1)
        return A[0];
    else {
        maior = maiorVetor(A, N-1);
        if(maior > A[N-1])
            return maior;
        else
            return A[N-1];
    }
}
int main () {
    int A[4] = {12, 65, 14, 38};

    printf("%d", maiorVetor(A, 4));

return 0;

}

ACCORDING TO ME, THIS IS WHAT HAPPENS IN THIS PROGRAM->

Explanation-(refer to the recursion tree diagram)

Step 1) (refer to the recursion tree diagram)

int maiorVetor(int A, int 4) {
    int maior;
    if(N == 1) // here 4!=1
        return A[0];
    else {
        maior = maiorVetor(A, N-1); //this is where recursion happens.

                                    //So,maior=maiorVector(A,4-1)=maiorVector(A,3)

                                    //Now here, we again call the maiorVector function 
                                    //with value maiorVector(A,3)

        /*So, for now we leave original function func. maiorVector(A,4) just at this 
        line, i.e , just before the if statement. 
        We'll touch this if statement and consequent statements again in Step 8.*/  

       if(maior > A[N-1]) /*LEFT FOR 
            return maior;   STEP 8*/
        else
            return A[N-1]; /*LEFT FOR STEP 8*/ 
    }
}

Step 2) (refer to the recursion tree diagram)

int maiorVetor(int A, int 3) {
    int maior;
    if(N == 1) // here 3!=1
        return A[0];
    else {
        maior = maiorVetor(A, N-1); //this is where recursion happens.

                                    //So,maior=maiorVector(A,3-1)=maiorVector(A,2)

                                    //Now here, we again call the maiorVector function 
                                    //with value maiorVector(A,2)

        /*So, for now we leave original function func. maiorVector(A,3) just at this 
        line, i.e , just before the if statement.
        We'll touch this if statement and consequent statements again in Step 7.*/  

       if(maior > A[N-1])
            return maior;
        else
            return A[N-1];
    }
}

Step 3) (refer to the recursion tree diagram)

int maiorVetor(int A, int 2) {
    int maior;
    if(N == 1) // here 2!=1
        return A[0];
    else {
        maior = maiorVetor(A, N-1); //this is where recursion happens.

                                    //So,maior=maiorVector(A,2-1)=maiorVector(A,1)

                                    //Now here, we again call the maiorVector function 
                                    //with value maiorVector(A,1)

        /*So, for now we leave original function func. maiorVector(A,2) just at this 
        line, i.e , just before the if statement.
        We'll touch this if statement and consequent statements again in Step 6.*/  

       if(maior > A[N-1])
            return maior;
        else
            return A[N-1];
    }
}

Step 4) (refer to the recursion tree diagram)

int maiorVetor(int A, int 1) {
    int maior;
    if(N == 1) // YES,HERE 1==1.SO WE REUTRN A[0]=12.
       return A[0]; //THE LOOP IS TERMINATED AND WE EXIT FROM mainVector(int A,int 1).
    else {
        maior = maiorVetor(A, N-1);           
       if(maior > A[N-1])
            return maior;
        else
            return A[N-1];
    }
}

Step 5) (refer to the recursion tree diagram)

/*From this step, we start coming out of the recursion. That, according to the 
Recursive tree diagram, we start moving in the reverse/upward direction.*/

    /*The value returned in step 4 from maiorVector(A,1)=12 is stored in the variable 
    maior in the first statement of else block.*/ 

    int maiorVetor(int A, int 2) {
        int maior;
        if(N == 1) // here 2!=1
            return A[0];
        else {
            maior = maiorVetor(A, N-1); // =maiorVector(A,2-1)=maiorVector(A,1)=12               

           if(maior > A[N-1])
                return maior;
            else
                return A[N-1];
        }
    }

Step 6) (refer to the recursion tree diagram)

//as told in Step 3, we had to come back in the maiorVector(A,2) in step 6.
int maiorVetor(int A, int 2) {
        int maior;
        if(N == 1) // here 2!=1
            return A[0];
        else {
            maior = maiorVetor(A, N-1); // =maiorVector(A,2-1)=maiorVector(A,1)=12               

           if(maior > A[N-1]) //if(12>A[2-1])-->if(12>A[1])-->if(12>65), which is 
                              //false
                return maior;
            else
                return A[N-1]; /*Since else part is true, we will return 65.

                               Also, this 65 is returned as the value for maior in the 
                               fucntion maiorVector(A,3) in step 7*/
        }
    }

Step 7) (refer to the recursion tree diagram)

//as told in Step 2, we had to come back in the maiorVector(A,3) in step 7.
int maiorVetor(int A, int 3) {
        int maior;
        if(N == 1) // here 3!=1
            return A[0];
        else {
            maior = maiorVetor(A, N-1); // =maiorVector(A,3-1)=maiorVector(A,2)=65               

           if(maior > A[N-1]) //if(65>A[3-1])-->if(65>A[2])-->if(65>14), which is 
                              //true. So return 65.


                return maior; /*Also, this 65 acts as the value for maior for the 
                               fucntion maiorVector(A,4)*/
            else
                return A[N-1]; //false, so not executed.
        }
    }

Step 8) (refer to the recursion tree diagram)

//as told in Step 1, we had to come back in the maiorVector(A,4) in step 8.
int maiorVetor(int A, int 4) {
        int maior;
        if(N == 1) // here 4!=1
            return A[0];
        else {
            maior = maiorVetor(A, N-1); // =maiorVector(A,4-1)=maiorVector(A,3)=65               

           if(maior > A[N-1]) //if(65>A[4-1])-->if(65>A[3])-->if(12>14), which is 
                              //true. So return 65.


                return maior; /*Now,this value 65 is returned and printed through the 
                              printf("%d",mainVector(A,4)); statement in the main 
                              function*/
            else
                return A[N-1]; //false, so not executed.
        }
    }

SO, YOUR OUTPUT IS

score 2 · Answer 2 · answered Mar 17 '20 at 15:58

As already commented, better idea to understand the flow of the code is use the debugger ( may be online one, given as ref link 3 below) to under stand the same.

In short, the maiorVetor(V, N-1) function is called recursively until it reaches the exit condition of recursion i,e, till N==1. In these steps, it will sort out the array of integer, A in descending order and returns the greatest number i.e, A[0].

Well, if you rally want to understand how recursion works and how it uses the stack please refer the below links:

Recursion in C - Largest element of an array

2 Answers2