Основные вопросы программы C ++ Recursion

Question

//This program finds the GCD of two numbers using a recursive function call via the
//Euclidean algorithm

#include <iostream>
#include <cmath>
using namespace std;

int GCD (int A, int B);

int main()
{
    int A = 45, B = 55;

    cout << "The GCD is " << GCD(A,B) << endl;
    //test
    return 0;
}

int GCD (int A, int B)
{
    A = abs(A);
    B = abs(B);


    if (A > B)
    {
        A = A - B;
        return GCD (A, B); //Recursive function call - works fine
        //GCD (A, B);  -- This function call seems to return an incorrect value

    else if (A < B)
    { 
        B = B - A;
        return GCD (A, B);//Recursive function call
        //GCD (A, B); -- This function call seems to return an incorrect value
    }

    else if (A = B)
    {
        return A;
    }
}

Вот мой вопрос: я заметил, что если я не использую ключевое слово «return» в моем рекурсивном вызове функции, программа возвращает неверное значение, но если я пошагово выполняю функцию, значения в локальном каталоге корректно обновляются. Я знаю, что функции (если они не относятся к типу void) должны возвращать значение. Возможно, это правило применимо и к рекурсивным вызовам функций?

Может, кто-нибудь уточнит / поможет мне понять?

Answer 1

Возможно, это правило применимо и к рекурсивным вызовам функций?

Почему должны применяться другие правила? Рекурсивные функции работают точно как обычные функции.

Кстати, ваша программа содержит ошибку:

else if (A = B)
{
    return A;
}

Это не сравнение, это задание, и, кроме того, проверка не нужна, поскольку все остальные условия (A < B и A > B) уже проверены.

Answer 2

Если вы не возвращаете значение, тогда не определено, какое значение возвращается. Поэтому, если ни один из ваших if / else if не соответствует, вы возвращаете непредсказуемое значение (зависит от флагов компилятора / компилятора / времени дня, когда вы запускаете свою программу / ...). Таким образом, вызывающий метод будет вычислять неверные результаты.

Это верно для рекурсивных и нерекурсивных методов и функций.

Answer 3

Способ обдумать это - использовать вложенные вызовы функций. Внешний GCD вызывает внутренний GCD, который, в свою очередь, вызывает внутренний GCD. Когда вы доберетесь до самого внутреннего вызова (тот, где A == B), вы получите return A, и этот возврат будет распространяться на все возвращаемые вами значения, пока не достигнет самого внешнего GCD, который вернет правильное значение. Без возвратов результат самого внутреннего вызова никогда не попадет во внешний мир.

Попробуйте записать, что функция делает с простыми значениями, и вы увидите это поведение вложенности.

Редактировать: если вы использовали Lisp, вы можете быть сбиты с толку, потому что Lisp автоматически возвращает последнюю строку функции.

Answer 4

Я знаю, что функции (если они не относятся к типу void) должны возвращать значение. Возможно, это правило применимо и к рекурсивным вызовам функций?

Да, это так. Если вы не используете оператор return, возвращаемое значение функции не определено.

Answer 5

" возможно, это правило применимо и к рекурсивному вызову "

Конечно, рекурсия не является особым случаем. Ваша функция должна что-то возвращать, и в этом случае это возвращаемое значение рекурсивного вызова, которое необходимо вернуть.

Есть еще одна тихая ошибка: вы написали (A=B) вместо (A==B)

Answer 6

В версии return GCD(A,B); результат вызова GCD(A,B) возвращается родителю. Если вы пропустите оператор return, то возвращенный результат будет потерян и не будет передан вызову GCD().

.

То есть в "C" вы должны использовать оператор return, чтобы функция возвращала значение.