Ajuda com função recursiva

[einstein]

Boa noite,

Estou a estudar o funcionamento de funções recursivas só que nao percebo bem como é que elas funcionam será que alguem me pode dar umas dicas? Tenho a seguinte função

:

int rec(int p)
{
if (p < 1)
return 0;
else
return p + rec(n / 2);
}

Eu não consigo perceber o seu funcionamento. Imagenos que ela recebe um argumento p=10, como 10 nao e menor do que 1 vai parar ao else, e agora o que eu nao sei é se ela retorna logo o valor p e depois vai executar a função outra vez ou se só retorna no final.

Outra duvida é no ultimo caso quando o p toma o valor 0 quando ela vai retornar vai retornar para onde? Para a linha onde foi invocada?

[pikax]

void forPrintRecursFront(int num)
{
 if(num<1)
 return;
 forPrintRecurs(num-1);
 printf("%d\n",num);
}

void forPrintRecursBack(int num)
{
 if(num<1)
 return;
 printf("%d\n",num);
 forPrintRecurs(num-1);
}

Ve se consegues perceber estas 2 funcoes.

Eu não consigo perceber o seu funcionamento. Imagenos que ela recebe um argumento p=10, como 10 nao e menor do que 1 vai parar ao else, e agora o que eu nao sei é se ela retorna logo o valor p e depois vai executar a função outra vez ou se só retorna no final.

Isso chama-se stack ou pilha.

Uma pilha é uma estrutura de dados que implementa a filosofia LIFO(Last In, First Out), ou seja, o último item a ser inserido na pilha é o primeiro a poder ser retirado, pois é o que se encontra por “cima”.

Basicamente uma funcao recursiva a primeira funcao ira' a ser a primeira a ser inserida na stack do programa e depois as outras irao ficar no topo, depois quando o p<1 for verdadeiro a pilha ira se esvaziar.

[HappyHippyHippo]

primeiro, vou assumir que te enganaste e usaste a variavel 'n' em vez da 'p'

segundo, uma maneira de perceber como isso funciona é assim

pega no códido da função e "espeta" no lugar da chamada da função:

int rec(int p)
{
 if (p < 1)
   return 0;
 else
   return p + rec(n / 2);
}

// primeira troca
int rec(int p)
{
 if (p < 1)
   return 0;
 else
   return p + (// dentro destes parênteses, onde aparece 'p' será trocado pelo p/2 (argumento da função)
               if ((p/2) < 1)  
                 return 0;
               else
                 return (p/2) + rec((p/2)/2); // p/2/2 = p/4
               );
}

// segunda troca
int rec(int p)
{
 if (p < 1)
   return 0;
 else
   return p + (// dentro destes parênteses, onde aparece 'p' será trocado pelo p/2 (argumento da função)
               if ((p/2) < 1)  
                 return 0;
               else
                 return (p/2) + (// dentro destes parênteses, onde aparece 'p' será trocado pelo p/4 (argumento da função)
                                 if ((p/4) < 1)  
                                   return 0;
                                 else
                                   return (p/4) + rec((p/4)/2); // p/4/2 = p/8
                                 );
               );
}

// e por ai a diante ...

espero que agora percebas como funciona uma função recursiva e qual a resposta a:

se ela retorna logo o valor p e depois vai executar a função outra vez ou se só retorna no final.

e

Outra duvida é no ultimo caso quando o p toma o valor 0 quando ela vai retornar vai retornar para onde? Para a linha onde foi invocada?

outra maneira de visualizar a resposta a estas perguntas é esta (e bastante simples)

int rec(int p)
{
 if (p < 1)
   return 0;
 else
   return (p + rec(p / 2)); // meti os parenteses extra mas é como se não tivessem lá
}

os parenteses dizem que primeiro resolve o que está dentro, e como o que está dentro é toda a expressão "p+rec(p/2)", logo sabes que primeiro é chamada a função, o resultado somado a 'p' e só depois retornado

[einstein]

Obrigado aos dois pelas respostas. Vamos ver se eu percebi. Da primeira vez que a função é chamada com o p=10 ela vai guardar na pilha o valor de 10 certo? Só depois quando chega a p<1 é que ela vai tirando os valores da pilha para os somar. É isto ?

[mundo]

Sim, e retorna o valor p