Рекурсивная двоичная функция в десятичную без функции pow () или циклов

Question

Я делаю курс Си. Мне нужно сделать рекурсивный двоичный файл XOR, но у меня есть некоторые ограничения. Я не могу использовать цикл или любые функции math.h, а также не могу вызвать другую функцию из функции XOR.

Это прототип функции:

int binaryXor(int firstnumber[], int secondnumber[], int length);

, где firstnumber и secondnumber - это массивы с одинаковой длиной 1 и 0, а length - их длина.

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

Answer 1

Чтобы написать рекурсивную функцию без циклов, вам нужно ответить на следующий вопрос:

«Как я могу выразить ответ на мою проблему в терминах меньшей задачи?»

В этом случае проблема в том, что у вас есть length цифр для просмотра, но вы не можете зацикливаться. Итак, как вы выражаете xor размера length в терминах меньшего xor вместе с некоторым объемом работы, который не требует цикла?

[Редактировать: подожди, только что снова посмотрел на твой вопрос, и ты сказал, что у тебя уже есть xor, так что, я думаю, ты уже сделал это. В этом случае мой комментарий выше - единственное, что вам нужно знать: вы закончили. int в C - это не десятичное значение, это просто значение. Вам не нужно преобразовывать что-либо в десятичное число, чтобы сохранить или вернуть его в int.

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

Answer 2

Это стандартный рекурсивный вопрос. Хитрость заключается в том, чтобы понять, что целочисленное значение строки 1 с и 0 с последующими 1 или 0, равно 2 * целочисленное значение строки плюс значение цифры.

Так что вы захотите сделать что-то вроде

if( length <= 0) return 0;

return 2 * binaryXOR(firstnumber, secondnumber, length - 1) + (firstnumber[length - 1] ^ secondnumber[length - 1]);

Answer 3

Вместо цикла можно использовать рекурсивный вызов функции.