Являются ли рекурсивные функции реентерабельными

Question

Я видел много рекурсивных функций (в основном используемых для вычисления некоторых математических операций, например, факториала, суммы цифр в числе и т. Д.), Которые включают использование статической переменной, которая содержит результат каждого рекурсивного вызова /операции, и использует его для последующих вызовов.

То же самое делает рекурсивные функции не рентабельными и не поточно-ориентированными.

Существуют ли другие случаи использования рекурсивных функций, которые не нужныстатические переменные?

Answer 1

Это разные понятия. Одно не подразумевает другого или наоборот.

Например, это рекурсивная функция (гипотетический язык)?

global sum = 0

proc accumulate(treeNode)
    sum += treeNode.Value
    if treeNode.Left then accumulate(treeNode.Left)
    if treeNode.Right then accumulate(treeNode.Right)
end

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

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

func accumulate(treeNode)
    sum = treeNode.Value
    if treeNode.Left then sum += accumulate(treeNode.Left)
    if treeNode.Right then sum += accumulate(treeNode.Right)
    return sum
end

Ничто не присуще концепции рекурсивной функции, которая делает ее не поточно-ориентированной или реентерабельной, или наоборот, все зависит от того, что вы на самом деле пишете в рассматриваемой функции.

Answer 2

Существуют ли другие случаи использования рекурсивных функций, для которых не нужны статические переменные .?

Конечно. Фактически, статические переменные в рекурсивных функциях должны быть исключением , а не правилом:

Я видел много рекурсивных функций (в основном используемых для вычисления некоторых математических операций, например, факториала, суммы цифр в числе и т. Д.), Которые включают использование статической переменной, которая содержит результат каждого рекурсивного вызова и использует его для последующих вызовов.

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

Answer 3

Примеры, которые вы видели, на мой взгляд, ошибочны. Стандартные средства написания рекурсивной функции не не используют и не требуют статической переменной для хранения результата; вместо этого вы должны использовать аргументы и / или возвращаемое значение. Использование статики действительно сделает их не арендными, но их не следует кодировать таким образом.

Пример использования возвращаемого значения (JavaScript):

function deepCollectChildText(node) {
    var text, child;

    text = "";
    for (child = node.firstChild; child; child = child.nextSibling) {
        switch (child.nodeType) {
            case 1: // element node, may contain child nodes
                text += deepCollectChildText(child);
                break;
            case 3: // text node
                text += child.value;
                break;
        }
    }
    return text;
}

Нет необходимости в статике. Он мог бы быть закодирован с использованием одного и, следовательно, не быть повторно входящим, но для этого нет причины

Answer 4

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

Answer 5

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

• Повторно поступающие функции не изменяют статические переменные или общие ресурсы и не читают статические неконстантные или изменяемые общие ресурсы.
• Следовательно, Re-entrant => поточно-ориентированный, но не наоборот.
• Рекурсивные функции, модифицирующие статические переменные, не являются реентерабельными.

Таким образом, повторяющиеся рекурсивные функции являются поточно-ориентированными. Хотя нерекурентные рекурсивные функции не являются поточно-ориентированными, за исключением случаев, когда доступ к общим / статическим ресурсам эффективно ограничен границами синхронизации.

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

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

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

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

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

Следовательно, мой вывод заключается в том, что до тех пор, пока статический / разделяемый ресурс распределяет уникальный экземпляр для каждого входа, функция возвращается.

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

Answer 6

ИМХО, если в функции используется статическая или глобальная переменная, она не может быть поточно-ориентированной. В противном случае это потокобезопасный.

Answer 7

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