Можете ли вы помочь мне с моей рекурсивной функцией? - PullRequest
Новая
       7

Можете ли вы помочь мне с моей рекурсивной функцией?

0 голосов
/ 11 апреля 2020

У меня есть эта простая функция, которую я правильно вычисляю, но мои выходные операторы выключены. Я пробовал в других местах комментировать оператор cout, но он не работает. 

int recursiveFunc(int n) {
    int val;    // value at nth sequence


    //cout << "(" << n << ") = " << val << endl;

    if (n == 1 ) {      // base case 1
        val = -1;
        // outputs before function call
    }
    else if (n == 2) {  // base case 2
        val = -1;
        // outputs before function call
    }
    else {      // recursive case
        //cout << "(" << n << ") = << val << endl;
        val = 2*(recursiveFunc(n-1) + recursiveFunc(n-2));
        cout << "(" << n << ") = " << val << endl;   // not sure where to put cout statement

    }

    return val;
}

Я ищу вывод, например (например, n = 5): 

(1) = -1
(2) = -1
(3) = -4
(4) = -10
(5) = -28

в настоящее время мой вывод выглядит так: 

(1) = -1
(2) = -1
(3) = -4
(4) = -10
(3) = -4    // here an nth term is displayed twice
(5) = -28

Ответы [ 3 ]

1 голос
/ 11 апреля 2020

Переместите ваш оператор cout за пределы функции, и он отлично работает. 

int recursiveFunc(int n) {
    int val;    // value at nth sequence

    if (n == 1) {      // base case 1
        val = -1;
    }
    else if (n == 2) {  // base case 2
        val = -1;
    }
    else {      // recursive case
        val = 2 * (recursiveFunc(n - 1) + recursiveFunc(n - 2));
    }

    return val;
}

int main() {
    for (int i = 1; i < 10; i++) {

        std::cout << "(" << i << ") = " << recursiveFunc(i) << endl;
    }
    return 0;
}

Вывод: 

(1) = -1
(2) = -1
(3) = -4
(4) = -10
(5) = -28
(6) = -76
(7) = -208
(8) = -568
(9) = -1552
0 голосов
/ 11 апреля 2020

вы должны использовать массив для хранения значений, которые вы вычислили, например 

const int N = 1000000;
int values[N]; // remember to memset to 0 first

int recursiveFunc(int n) {
    if(n < 0) return 0;
    if(values[n] != 0) return values[n];

    int val;    // value at nth sequence

    if (n == 1) {      // base case 1
        val = -1;
    }
    else if (n == 2) {  // base case 2
        val = -1;
    }
    else {      // recursive case
        val = 2 * (recursiveFunc(n - 1) + recursiveFunc(n - 2));
    }

    return values[n] = val;
}

int main() {
    memset(values, 0, sizeof(values));
    for (int i = 1; i < 10; i++) {

        std::cout << "(" << i << ") = " << recursiveFunc(i) << endl;
    }
    return 0;
}
0 голосов
/ 11 апреля 2020

С самого начала, возможно, исправление состоит в том, чтобы отслеживать самый высокий выход n до сих пор и выводить только тогда, когда встречается больший n. (Возможно, это не самое лучшее решение 1004 *, но я чувствую себя слишком уставшим и ленивым, чтобы думать об альтернативах)

Не используйте глобальную переменную для этого ( изменяемое глобальное состояние является анти-шаблоном! ) - вам нужно будет передать его в качестве другого параметра. 


int output_n_and_val( int n, int val, int& biggestN ) {

    if( n > biggestN ) {
        cout << "(" << n << ") = " << val << endl;
        biggestN = n;
    }
    return val;
}

int recursiveFuncImpl( int n, int& biggestN ) {

    if( n == 1 ) {
        return output_n_and_val( n, -1, biggestN );
    }
    else if( n == 2 ) {
        return output_n_and_val( n, -1, biggestN );
    }
    else {
        int val =  2 * ( recursiveFuncImpl( n - 1, biggestN ) + recursiveFuncImpl( n - 2, biggestN ) );
        return output_n_and_val( n, val, biggestN );
    }
}

// Entrypoint function:
int recursiveFunc( int n ) {

    int biggestN = -1;
    return recursiveFuncImpl( n, biggestN );
}

int main()
{
    recursiveFunc( 10 );

    recursiveFunc( 5 );

    return 0;
}

Недостатком этого подхода является то, что из-за n == 2 происходит обработка регистра до n == 1 вы никогда не получите вывод (1) = -1. Исправление это упражнение, оставленное для читателя.

...