Función binaria recursiva a decimal sin pow () o bucles

Question

Estoy haciendo un curso de C. Necesito hacer un binario XOR recursivo pero tengo algunas limitaciones. No puedo usar el bucle ni ninguna función math.h, ni puedo llamar a otra función desde la función XOR.

Este es el prototipo de la función:

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

donde firstnumber y secondnumber son matrices con la misma longitud de 1s y 0s y length es su longitud.

La función debería devolver el valor decimal del XOR de esas dos matrices. Hacer el XOR es bastante simple, pero ¿cómo puedo convertirlo a decimal con todas las limitaciones?

Answer 1

Esta es una pregunta recursiva estándar. El truco consiste en darse cuenta de que el valor entero de una cadena de 1s y 0s seguido de 1 o 0, es 2 * el valor entero de la cadena más el valor del dígito.

Entonces querrás hacer algo como

if( length <= 0) return 0;

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

Answer 2

Para escribir una función recursiva, sin bucles, debe responder la siguiente pregunta:

`` ¿Cómo puedo expresar la respuesta a mi problema en términos de un problema menor? ''

En este caso, el problema es que tiene que mirar los dígitos de length , pero no tiene permitido hacer un loop. Entonces, ¿cómo se expresa un xor de tamaño length en términos de un xor más pequeño, junto con una cantidad de trabajo que no requiere un bucle?

[Editar: espera, solo miraste tu pregunta nuevamente y dices que ya tienes el xor ordenado, así que supongo que ya lo has hecho. En ese caso, mi comentario anterior es lo único que necesita saber: ha terminado. Un int en C no es un valor decimal, es solo un valor. No necesita convertir nada a decimal para almacenarlo o devolverlo en un int .

Sin embargo, si está interesado, puedo publicar un código que convierta un int en un valor decimal utilizando una función recursiva. Una manera simple es hacer ejercicio en el camino "hacia abajo" cuántos dígitos se requieren, comparando con potencias cada vez mayores de 10, y luego en el camino de regreso '' arriba '' imprime los dígitos comenzando desde el final.]

Answer 3

Se puede usar una llamada de función recursiva en lugar de un bucle.