Reentrancy and recursion

Question

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

Answer 1

Совсем нет.

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

Рассмотрим:

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); 
} 

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

Answer 2

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

global i; 

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

    } 

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

Answer 3

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

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

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

So: no.

Answer 4

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

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

Answer 5

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

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