Alguem sabe como fazer uma multiplicacao recursiva?

Eu preciso escrever uma função recursiva que aceita dois argumentos para os parâmetros x e y. A função deve retornar o valor de x vezes y. Uma dica dada, diz que a multiplicação pode ser realizada como adições repetidas como 7 4 = 4 + 4 + 4 + 4 + 4 + 4 + 4. Isso é C++ microsoft visual Studio 2008.

Resposta

Siga a dica.

x 1 = x, mais

x n = x + (x (n - 1))

E há a recursão. Nós pode código como este:

int multiply2 (int x, int n)

{

se (n = = 1) retorno x;

outro retorno x + multiply2 (x, n - 1);

}

mas isso, naturalmente, apenas aborda n positivo. Para lidar com o negativo n e 0 também, podemos criar um outro, mais geral, a função:

multiplicar de int (int x, int n)

{

se (x = = 0) retorna 0;

se (n = = 0) retorna 0;

se (n< 0)="" {="">

x = - x;

n = - n;

}

retornar multiply2 (x, n);

}

Porque, 5 -2 é o mesmo que -5 2, e, se x ou n é 0, a resposta é 0.

Edit - Nós agora modificar este é muito mais eficiente. Primeiro, nós mudamos a multiplicar para enviar apenas números positivos para multiply2(). Observe que um número ímpar de números que são negativo dar um negativo quando multiplicado! Em seguida, podemos mudar multiply2() para chamar esta função só será recurse para o número de bits de russian_peasant() (em outras palavras, apenas 31 vezes, máximos). Google-lo... é como a maioria dos multiplicadores de hardware são implementados. Aviso que precisávamos para acumular r no cálculovai se livrar disso logo.

#include<stdio.h>

int russian_peasant (int x, int n, int r)

{

se (n = = 0) retornar r;

se (n & 1) r + = x;

russian_peasant de retorno (x < 1,="" n=""> </>> 1, r);

}

int multiply2 (int x, int n)

{

retornar russian_peasant (x, n, 0);

}

multiplicar de int (int x, int n)

{

sinal de int = 0;

int r;

se (x = = 0) retorna 0;

se (n = = 0) retorna 0;

se (x< 0)="" {="" x="-x;" ++sign;="" }="">

se (n< 0)="" {="" n="-n;" ++sign;="" }="">

r = multiply2 (x, n);

se (sinal de & 1) r = - r;

retorno r;

}

int main (void)

{

printf ("%d\n", multiply(3, 4));

retorno 0;

}

=============

E agora para eliminar o "r". Note-se que x é adicionado somente se n é ímpar, então nada é adicionado. No final da recursão, podemos adicionar 0. Então, isso elimina a variável "r":

int russian_peasant (int x, int n)

{

se (n = = 0) retorna 0;

outra coisa se retornam (n & 1) x + russian_peasant (x < 1,="" n=""> </>> 1);

outro retorno russian_peasant (x < 1,="" n=""> </>> 1);

}

e isto permite colocar essa rotina em exatamente para a rotina de "multiply2()" original.

Editar = = =

Observações finais.

1 - O multiply2() recursiva e rotinas de russian_peasant() final não modificam todas as variáveis. Eles são puramente funcional. Nossa primeira definição de russian_peasant() modificado a variável "r", mas pode ser facilmente modificada para não modificar a variável. Considere esta mudança (r + = x é alterado para uma chamada recursiva):

int russian_peasant (int x, int n, int r)

{

se (n = = 0) retornar r;

se (n & 1) retornam russian_peasant (x < 1,="" n=""> </>> 1, r + x);

russian_peasant de retorno (x < 1,="" n=""> </>> 1, r);

}

Vendo que isso faz com que a versão do russian_peasant() sem "r" um pouco mais claro, espero.

No entanto, a versão com "r" é mais fácil de converter em formas interativas:

int russian_peasant (int x, int n)

{

int i = 0;

ao mesmo tempo o (n) {

se (n & 1) r + = x;

x<= 1;=""></=>

n >> = 1;

}

retorno r;

}

mas, observe que a definição recursiva é mais fácil de ler! Além disso, observe que a solução iterativa foi uma simples mudança mecânica - estou (quase) certeza de que é correto, apesar de eu nunca ter incomodado mesmo tentá-lo.

2 - Pense sobre o caso multiply(1000,1000). multiply2() será recurse 1000 vezes para fazer isso, enquanto russian_peasant será recurse 12 vezes. Isso que russian_peasant() cerca de 10 vezes mais rápido neste caso. A recursão máxima em russian_peasant() é 31 (para um de 32 bits assinado int), enquanto multiply2() pode incluir até 2 bilhões de vezes. Este aumento é eficiência (até quase 100 milhões de vezes mais rápido de 32 bits e ainda mais para 64 bits ou mais) por isso achei importante lhe apresentar o novo algoritmo.

3 - Desde o comportamento dos >> e talvez até mesmo< shift="" operations="" may="" be="" inconsistent="" with="" negative="" numbers,="" when="" we="" implemented="" russian_peasant()="" we="" made="" sure="" that="" both="" numbers="" were="" positive,="" and="" adjusted="" the="" sign="" on="" return.="" this="" is="" not="" really="" needed,="" but="" is="" just="" good="" portability="" practice.="">

4 - Nós cobrimos muito neste breve ensaio. Formulações recursivas, programação funcional Fundamental, manipulações simples de funções, desempenho de algoritmos, considerações de portabilidade. Dar um passo por vez.</stdio.h>