Quel type de récursivité est une déclaration de retour avec un "OU"?

Question

Voici mon pseudo-code pour un programme récursif qui déplace un cercle à droite ou à gauche d'un tableau. J'essaie de comprendre la complexité (ce que je pense est n, la taille du tableau A, ou pourrait-elle être 2^n puisqu'elle peut soit retourner à gauche ou à droite?). J'essaie également de comprendre quel genre de récursion c'est, car il a un OU dans la dernière déclaration de retour, mais je ne trouve nulle part d'information à ce sujet.

Boolean rightWing (int circle, Array A, List<int> checkerList) 

Integer lastPlace equals A.length - 1 

If circle equals lastPlace then // base case for recursion 
    Return true 

If circle < 0 then 
    Return false 

If circle > lastPlace then 
    Return false 

// impossible case 
If checkerList contains (circle) returns True then 
    Return false 

checkerList.add(circle) // add the circle to the list for the checker if it's an impossible case 

Integer moveRight equals circle + A[circle] 
Integer moveLeft equals circle - A[circle] 

Return rightWing (moveRight, A, checkerList) or rightWing(moveLeft, A, checkerList) 

Answer 1

Je ne suis pas sûr que votre algorithme est correct, mais d'après ce que vous avez dit je pense que vous allez vérifier chaque élément de votre choix une fois si O (n) avec n = sizeof (A) est correct.

Le type d'appel recusif que vous recherchez est récursif ou non récursif. What is tail recursion?