Problema com Recursividade

[Cyberlacs 0]

Amigos estou tentando resolver este problema mas, não consegui, gostaria de saber a solução do exercício abaixo.

 

Seja uma liguagem hipotética na qual não existem operadores para adição, nem subtração, porem existe uma função para incrementar um valor (INC(4)retorna 5). Defina uma função recursiva que ao receber dois numeros naturais X e Y, retorne a soma dos elementos. Em seguida, mostre como a recursão de cauda pode ser eliminada pode ser eliminada da função usando uma implementação iterativa(com comando de repetição).

Observação; se um dos valores numa soma é zero o resultado só pode ser o outro valor. Por outro lado, se ambos forem diferentes de zero, podemos ir tirando unidades dos primeiro e ir passando para o segundo; eventualmente o primeiro torna-se zero, e o segundo conterá o resultado da soma.

Estou com dúvidas neste exercício.

Desde já agradeço.

[_Isis_ 202]

Estou com dúvidas neste exercício.

 

gostaria de saber a solução do exercício abaixo.

 

 

Vc está com dúvidas no exercício ou quer a solução pronta?

[Cyberlacs 0]

Viu _Isis_ ja tentei fazer refazer e não consegui a solução, se alguém me arrumasse a solução ficaria grato.

 

Sei que não é correto mas, não consegui mesmo a solução.

 

Olha o que EU fiz esta errado tem variável global e meu professor não gosta muito disso :)

 

//retitar de uma lista e inserir em outra
#include <stdio.h>
#include<conio2.h>
#include <ctype.h>
#include <stdlib.h>

int a = 0;//VARIÁVEL GLOBAL :(

int creck()
{
    return a++;
}

int rec(int x, int y)
{
    if(creck() < x)
    {
         printf("%d/n",rec(x,y));
    }
    else if(creck() < y)
    {
         printf("%d/n",rec(x,y));
    }
    else
        return creck();
}

int main()
{	
	rec(3,5);
    
    printf("&d",creck());
	
    getch();
}

Fico no aguardo

[_Isis_ 202]

Ter variável global não classifica o código como correto ou não (a não ser que o exercício peça explicitamente p/ que não tenha).

 

O que deixou um pouco confuso foi definir uma função que incrementa porque não existem operadores de adição/subtração e usar um '++' no código.

 

 

#include <stdio.h>

/* Soma binária. */
int inc(int x, int tmp) {
    if (!tmp)
       return x;
    return inc(x ^ tmp, (x & tmp) << 1);
}

int main(void) {
    printf("%d\n", inc(38,93));
    return 0;
}

[Cyberlacs 0]

Viu _ISIS_

 

Veja abaixo em vermelho o que o exercício propõe, não sei se você na sua resolução aplicou todos os quesitos

 

 

Seja uma liguagem hipotética na qual não existem operadores para adição, nem subtração, porem existe uma função para incrementar um valor (INC(4)retorna 5). Defina uma função recursiva que ao receber dois numeros naturais X e Y, retorne a soma dos elementos. Em seguida, mostre como a recursão de cauda pode ser eliminada pode ser eliminada da função usando uma implementação iterativa(com comando de repetição).

 

Observação; se um dos valores numa soma é zero o resultado só pode ser o outro valor. Por outro lado, se ambos forem diferentes de zero, podemos ir tirando unidades dos primeiro e ir passando para o segundo; eventualmente o primeiro torna-se zero, e o segundo conterá o resultado da soma.

 

 

 

Pelo que Eu entendi temos que ter estas três resolução para contextualizar o problema

1. 
   
2. para adição, nem subtração.
   
3. função para incrementar um valor (INC(4)retorna 5)
   
4. função recursiva que ao receber dois numeros naturais X e Y
   

Obrigado por esta me ajudando

 

Agradeço muito mesmo.

 

 

 

Caro _ISIS_ continue me ajudando estou precisando muito.

 

 

 

 

Fico no aguardo

 

Obrigado.

[guidjos 65]

A variável "a", no seu código, não é global.

 

Não existem variáveis globais em C.

[Cyberlacs 0]

 

 

Amigo guidjos

 

 

 

Gostaria de saber qual a solução para o problema acima.

 

Outra pergunta o que fiz acima esta correto ou será que existe outra maneira para fazer a resolução ?

 

 

Fico no aguardo, observo que este é o unico forum que pelo menos estamos discutindo referente a esta duvida a IMASTERS esta muito bem representada pelos seus integrantes.

 

Obrigado por responderem.

 

 

Ola será que alguem pode me ajuda ?

 

 

 

Fico no aguardo

[deep2 4]

Você já foi ajudado, a solução que a _Isis_ apresentou esta correta, ela não violou nenhuma das condições que o exercício estabeleceu. O único porem, é que ela não usou uma função de incremento, mas pelo que eu entendi não era requisito e sim uma das possibilidades de resolução.

[_Isis_ 202]

Função de incremento? Eu criei uma recursiva, como o exercício pede. Mas como uma das restrições é que a linguagem não possui operadores p/ adição nem subtração, não se pode usar x++, ++x, x-- e --x. O que resta, até onde eu conheço, é usar os operadores bitwise.

 

Agora é fazer a versão iterativa. O miolo do código (somador, condições) vc já tem.

[deep2 4]

Sim _Isis_, função de incremento. O exercício simplesmente fala que tal função existe, como ela é implementa pela hipotética linguagem, não vem ao caso, pelo que eu entendi, deve existir nessa linguagem também uma função de decremento, pois no exercício esta assim:

 

"podemos ir tirando unidades dos primeiros ..."

 

Bom, eu implementei assim:

 

http://pastebin.com/72tzhffp

 

PS: não sei como copiar o código fonte pro post.

[_Isis_ 202]

pelo que eu entendi, deve existir nessa linguagem também uma função de decremento, pois no exercício esta assim:

 

"podemos ir tirando unidades dos primeiros ..."

 

Nunca assumo nada de enunciado. Reprovações na universidade rlz.

Então, pelas restrições do enunciado, teu código estaria errado. Mesmo préfixado ou pósfixado, ++ ainda é +1, utilizando operador de soma, que não existe nessa linguagem. Por isso comentei que o enunciado era meio confuso. Ainda, se ambas as funções existirem, ao meu ver, o exercício não tem muito propósito, porque o funcionamento delas é igual a ter os operadores de adição e subtração disponíveis. Virou uma complicação desnecessária misturada com recursão.

 

O que consigo fazer só com a função inc é isso:

 

 

#include <stdio.h>

int recursive_sum(int x, int y) {
   if (!y) return x;
   return recursive_sum(inc(x), inc(y));
}

int main(void) {
   printf("%d", recursive_sum(73, ~10+1));
   return 0;
}

 

Repare que eu uso bitwise p/ gerar o negativo e depois incrementar até zero ao invés de subtrair a variável que funcionaria como contador dentro de um loop.

[Cyberlacs 0]

_ISIS_ a função inc seria qual em seu entendimento ?

 

 

O que seria isso no seu código?

return inc(x ^ tmp, (x & tmp) << 1); // O que é isso???? (x & tmp) << 1

#include <stdio.h>

/* Soma binária. */
int inc(int x, int tmp) {
    if (!tmp)
       return x;
    return inc(x ^ tmp, (x & tmp) << 1);
}

int main(void) {
    printf("%d\n", inc(38,93));
    return 0;
}

[_Isis_ 202]

A questão não é definir a função inc, e sim definir uma função recursiva que soma dois números. O que ela usa é a função inc.

 

(x & tmp) << 1

Um and bit a bit e um shift p/ a esquerda. Um carry.