Не могу понять, как «возвращение» работает

Question

Я изучаю следующий код, который призван выяснить решения х и у в расширенном Евклида алгоритм:

long gcd(long a, long b, long &x, long &y) { 
    long d; // place to hold final gcd 
    // in case b = 0, we have d=|a|, x=1 or -1, y arbitrary (say, 0) 
    if (b==0) { 
     if (a<0) { 
      d = -a; 
      x = -1; 
      y = 0; 
     } else { 
      d = a; 
      x = 1; 
      y = 0; 
     } 
     return d; 
    } 
    // if b is negative, here is a workaround 
    if (b<0) { 
     d = gcd(a,-b,x,y); 
     y = -y; 
     return d; 
    } 
    // if a is negative, here is a workaround 
    if (a<0) { 
     d = gcd(-a,b,x,y); 
     x = -x; 
     return d; 
    } 
    // set up recursion 
    long aa = b; 
    long bb = a%b; 
    long qq = a/b; 
    long xx,yy; 
    d = gcd(aa,bb,xx,yy); 
    x = yy +1; 
    y = xx - qq*yy; 
    return d; 
} 

То, что я действительно не понимаю как работает «return d». Учитывая два ввода номера (a, b), я пытаюсь следовать всем поведением, рассматривающим сеанс отладки (используя Apple Xcode).

Когда б == 0, то здесь идет:

if (b==0) { 
    if (a<0) { 
     d = -a; 
     x = -1; 
     y = 0; 
    } else { 
     d = a; 
     x = 1; 
     y = 0; 
    } 
    return d; 
} 

и от этого «возвращения д» он подскакивает до последнего «возвращения г» в конце кода. Оказавшись там, он начинает цикл этот последний кусок кода:

d = gcd(aa,bb,xx,yy); 
    x = yy +1; 
    y = xx - qq*yy; 
    return d; 
} 

пока все решения не будут найдены.

Мой вопрос являются:

1) почему с первого «возвращения д» он скачет прямо до последнего «возвращения д»? 2) как может быть возможно, что оттуда он остается в последние четыре строки до конца, вместо того, чтобы вызвать функцию

d = gcd(aa,bb,xx,yy); 

как это было сделано раньше?

Здесь я выкладываю также основное:

int main() { 

    long a,b,x,y; 

    cout << "Insert first ---> "; 
    cin >> a; 

    cout << "Insert second ---> "; 
    cin >> b; 




    cout << "The gcd of " << a << " and " << b << " is " 
     << gcd(a,b,x,y)<<endl; 

    cout << "x is " << x << " and y is " << y << endl; 

    return 0; 
} 

спасибо

Answer 1

1. Когда вы шаг от return d;, вы должны закончить в конце функции, которая является его закрывающей скобкой.

   Если вы начинаете закрывать фигурные скобки на своей собственной линии, вы сможете отличить «последнее утверждение» и «конец функции».

2. Рекурсивные функции работают точно так же, как нерекурсивные функции - каждый вызов возвращается к точке сразу после этого вызова; в вашем случае каждый звонок до gcd(aa,bb,xx,yy); вернется к строке x = yy +1;, и именно поэтому вы думаете, что эти линии зацикливаются.

   (Если вы откроете окно CallStack отладчика, вы увидите, что он растет, как называются функции и сжимается, как вы возвращаетесь из них, и вашей «петли» является возвращением к той же точке, в нескольких отдельных функциональных вызовов .)

Answer 2

Существует последовательные звонки на него в основном? Это единственная причина, по которой я могу понять, что она это сделает. Например:

long g1 = gcd(3, 0, x, y); 
long g2 = gcd(3, 2, x, y); 

Это, в теории, причиной того, что первое, если заявление, чтобы быть правдой, и оценить как таковой, а затем второй вызов НОД бы обойти все из если заявления и идти прямо на дно.

Редактировать: Я полагаю, что я действительно не понимаю этот вопрос и не должен был пытаться ответить. Тем не менее, то, что я знаю, что из кода при условии, есть четыре возможных пути, которые НОД могут принять, когда называют:

1. b==0 Это возвращает абсолютное значение a и устанавливает x = -1 если a был отрицательным (или 1 если нет, очевидно).
2. b<0 Это возвращает результат вызова gcd с абсолютным значением b и отменяет переменную y, переданную по ссылке.
3. a<0 То же, что и путь 2, но с a и x вместо b и y.
4. Ничто из перечисленного не является истинным, и случается странное дело (мне не пришлось использовать этот алгоритм (я знаю, я простой)).

Это, вероятно, не очень хорошо отвечает на ваш вопрос, но я всегда нарушаю эти проблемы для анализа и устранения неполадок, поэтому я надеюсь, что это было полезно, по крайней мере, для ознакомления с шагами, пошаговый метод устранения неполадок, если вы еще не использовали его.