Повторный вход и рекурсия

Question

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

Answer 1

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

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

Answer 2

«Reentrant» обычно означает, что функция может быть введена более одного раза одновременно двумя разными потоками.

Чтобы быть реентерабельной, она должна выполнять такие действия, как защита / блокировка доступа к статическому состоянию.

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

Итак: нет.

Answer 3

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

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

Answer 4

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

global i;

    factorial()
    { if i == 0 return 1;
      else { i = i -1; return i*factorial();

    }

Эта функция является рекурсивной и не реентерабельной.

Answer 5

Совсем нет.

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

Рассмотрим:

sem_t mutex;
int calls = 0;

int fib(int n)
{
    down(mutex); // lock for critical section - not reentrant per def.
    calls++; // global varible - not reentrant per def.
    up(mutex);

    if (n==1 || n==0)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

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