преобразование общей рекурсии в хвостовую рекурсию из-за переполнения стека для больших входов - PullRequest
Новая
       43

преобразование общей рекурсии в хвостовую рекурсию из-за переполнения стека для больших входов

0 голосов
/ 17 января 2020

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

Вот мой найденный алгоритм: 

#include<iostream>
using namespace std;
int foo(int);
int main(){
    int n;
    cin>>n;
    cout<<foo(n);
    return 0;
}
int foo(int n){
    int p=n/2-2;
    int t;
    if(p%6<5&&p%6>0)
        t=(p+6-p%6)/6;
    else if(p%6==5)
        t=(p+6-p%6)/6+1;
    else
        t=p/6;
    if(n==3||n==5||n==6)
        return 1;
    else if(n==4)
        return 0;
    else{
        if(n%2==0)
            return foo(n-3);
        else
            return foo(n+1)+t;
    }
}

1 Ответ

1 голос
/ 17 января 2020

Проблема здесь: 

return foo(n+1) + t;
//              ^^^

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

return foo(n + 1, t);

Чтобы сделать совместимым другой рекурсивный вызов, вы просто предоставите нейтральный элемент добавления: 

return foo(n-3, 0);

Подпись новой функции: 

int foo(int n, int offset = 0); // default parameter allows for calling just as before.

Последний вопрос: где делать сложение ???

Ну, два места очевидны: 

if(n==3||n==5||n==6)
    return 1 + offset;
else if(n==4)
    return /*0 +*/ offset;

offset - это накопленное смещение всех предыдущих рекурсивных вызовов! Поэтому вам придется добавить его к тому, что вы добавляете к рекурсивному вызову следующей функции, так: 

// ...
else if(n % 2 == 0)
    return foo(n-3, /*0 +*/ offset);
else
    return foo(n+1, t + offset);

Примечание: ваш алгоритм не подходит для отрицательных чисел. Вызов (неизмененный) foo с этими значениями заканчивается повторением до переполнения стека (если бы стек был достаточно большим, это могло бы привести к неопределенному поведению из-за целочисленного переполнения со знаком). Если вы не собираетесь использовать его для отрицательных чисел, вы абсолютно должны использовать unsigned int в качестве типа данных! В противном случае требуется соответствующее исправление.

Значения 0, 1 и 2 также требуют специальной обработки, они также приводят к отрицательному значению n (для неизмененного foo см. Выше). Но вы можете сделать это почти тривиально: 

if(n == 4)
{ ... }
else if (n < 6)
{ ... }

Это вернет 1 для n, равного 0, 1 или 2 (даже с версией, оптимизированной для хвостового вызова, так как смещение будет равно 0) и даже сэкономит некоторые сравнения. Если вам нужно вернуть 0 для специальных значений: также просто: 

else if (n < 6)
    return (n >= 3) + offset;

Вы можете даже объединить все в одно условие: 

if(n < 6)
    return (n == 3 || n > 4) + offset; // returning 0 for 0, 1, 2
    return (n <= 3 || n > 4) + offset; // returning 1 for 0, 1, 2

Наибольшее преимущество: во всех этих рекурсиях вам нужна только одна проверка, тогда как все остальные выполняются только при выполнении условия остановки (т. е. только один раз).

И вы можете переместить вычисление на p и t за условием остановки (с). ), вы все равно их там не используете ...

...