Expliquer la récursivité dans cet algorithme?

Question

Je sais que cet algorithme est pour trouver l'élément majoritaire de n'importe quel tableau s'il en a. Quelqu'un peut-il s'il vous plaît expliquer les appels de récursivité?

if length(A) = 0 then 
    return null 
end if 

if length(A) = 1 then 
    return 1 
end if 

// "Command 7" 
Call FIND-MAJORITY recursively on the first half of A, and let i be the result. 

// "Command 8" 
Call FIND-MAJORITY recursively on the second half of A, and let j be the result. 

if i > 0 then 
    compare i to all objects in A(including itself); 
    let k be the number of times that equality holds; 
    if k > length(A)/2 then 
    return i. 
    end if 
end if 

if j > 0 then 
    compare j to all objects in A(including itself); 
    let k be the number of times that equality holds; 
    if k > length(A)/2 then 
    return j 
    end if 
end if 

return null 

est-commande 7 est exécutée jusqu'à ce qu'il obtenir une valeur unique ... et commande alors 8? Je ne peux pas comprendre ces récursions. S'il vous plaît expliquer avec exemple, merci.

Answer 1

It depends what are inputs of this function. 
If the array A is an input then we only search in the diminished array else if the array A is defined as global then you always search the whole array. 

For example take the array A is 1,2,1,3,1,8,7,1 

If the array is given as input to the function : 

According to recursion we get A is 1,2,1,3 -> A is 1,2 -> A is 1 
This returns i := 1. 
Then A is 2, this returns j:=1. 
Then we compare i to all elements of A i.e 1,2. 
Then we compare j to all elements of A i.e. 1,2. 
We return null from this recursive call. 
After this we proceed to upper recursion i.e. 1,2,1,3 and up to the first call. 

If the array is global: 
According to recursion we get A is 1,2,1,3 -> A is 1,2 -> A is 1 
This returns i := 1. 
Then A is 2, this returns j:=1. 
Then we compare i to all elements of A i.e. 1,2,1,3,1,8,7,1 
we return according to the conditions. 

**Remember even in this case we return all recursive calls and check the whole array for every recursive call which is not what you probably want.