Это хвостовая рекурсия? - PullRequest
Новая
       2

Это хвостовая рекурсия?

1 голос
/ 19 февраля 2011

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

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
        int result = 0;
        if ( n > 0 )
            result = takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
        else if ( n == 0)
            result = mod ( coef , module );
        return result;
    }

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

Вот еще одна функция, использующая чисто рекурсию, которая, я думаю, отличается от приведенной выше: 

int takeModulusNORMRECURSION(int x, int n, int module){
    if ( n == 1 )
        return mod( x, module );
    else {
        int total = x * takeModulusNORMRECURSION( x, n - 1, module);
        return mod( total, module);
    }
}

Кстати, любойможете показать мне, как проверить стек кадров в Eclipse в этих случаях?как я пытался (не знаю, правильно или неправильно), и они оба берут много стеков.

Ответы [ 3 ]

0 голосов
/ 24 марта 2011

Первый метод является хвостовой рекурсивной, потому что когда функция выполняет return, возвращаемое ей значение является значением, которое не зависит от вызова другого метода в то время.

Второй метод не является хвостовой рекурсией и фактически не является рекурсивным, поскольку он просто повторяет изменяющиеся значения x.

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

Надеюсь, это поможет.

0 голосов
/ 10 марта 2014
  1. Хвосто-рекурсивный, возвращает непосредственно результат хвост-рекурсивного вызова
  2. Не является рекурсивным и, следовательно, даже не хвостовым рекурсивом
  3. Не является хвост-рекурсивным. Не возвращает результат рекурсивного вызова, но обрабатывает результат дальше.
0 голосов
/ 19 февраля 2011

Является ли это хвостовой рекурсией, зависит от того, как код скомпилирован.

Хвостовая рекурсия происходит, когда вы непосредственно возвращаете вызов другой функции (возможно, себе). Оптимизация вызова хвоста (причина, по которой люди заботятся о хвостовой рекурсии) происходит, когда компилятор / интерпретатор замечает это и просто заменяет текущий кадр стека, а не создает другой. В вашем случае, если он скомпилирован наивно, у вас нет хвостовой рекурсии, потому что вы делаете рекурсивный вызов, а затем присваиваете его переменной в стеке вызовов, которую вы позже вернете. Этот шаг присваивания означает, что вы выполняете дополнительные действия после вызова другой функции, что делает ваш код не подходящим для оптимизации хвостового вызова.

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

int takeModulusTAILRECURSION(int coef, int x, int n, int module){
    if ( n > 0 )
        return takeModulusTAILRECURSION( mod(coef * x, module), x , n - 1, module  );
    else if ( n == 0)
        return mod ( coef , module );
    else
        return 0;
}

//take modul of an integer ( both negative and positive )
int mod(int x, int modul){
    while ( x < 0) 
        x += modul;
    return x % modul;
}

Теперь это хвостовая рекурсия.

Но может ли теперь произойти оптимизация хвостового вызова, зависит от языка и реализации. Например, если ваш код должен быть Java, тогда как Предотвращает ли JVM оптимизацию хвостовых вызовов? указывает, что вы не собираетесь получать оптимизацию хвостовых вызовов независимо от того, что вы делаете.

Редактировать : Я говорил "хвостовая рекурсия" для "хвостовой рекурсии и хвостовой оптимизации оптимизированы".

...