Estou tentando descobrir como as recursões duplas funcionam no exemplo a seguir:
#include <iostream>
#include <vector>
int F(std::vector<int> &v, int a, int &b) {
if (a <= 0 || b <= 2) return a;
b -= 1;
a = F(v, a - 1, b) + F(v, a, b);
v.push_back(a);
return a;
}
int main(){
std::vector<int> v;
int b = 7;
F(v, 15, b);
for(int i=0;i<v.size();i++)
std::cout<<v[i]<<" ";
}
SAÍDA:
21 33 46 60 75
Eu entendo como 21 foi empurrado para dentro do vetor. Mas depois disso, não entendo qual recursão (esquerda ou direita) é então chamada, e como seguir isso até a saída correta.
Você poderia me explicar, passo a passo, como esse programa específico é executado?
Para registro:
O canto do advogado da língua
O exemplo infelizmente é UB , porque na expressão:
v e b são passados por referência e, de acordo com o código, estão sujeitos a efeitos colaterais :
Então, a avaliação do termo esquerdo e direito do
operator+naquela expressão não é sequenciada e não é necessariamente avaliada da esquerda para a direita. Em texto simples, o compilador pode escolher qualquer termo para calcular primeiro:E efeitos colaterais não sequenciados no mesmo local de memória são UB , que é o caso de v que ambas as chamadas de função modificam:
Isso significa que tudo pode acontecer, inclusive obter resultados diferentes de uma chamada para outra ou (mesmo que improvável neste caso) uma falha!
Observe que essas regras de sequenciamento são diferentes de idioma para idioma
Como corrigir sua recursão dupla?
A maneira mais simples seria forçar um sequenciamento, separando as chamadas recursivas em duas instruções diferentes:
Você pode então especificar completamente a ordem da recursão dupla trocando as linhas 1 e 2, se desejar.
Outra abordagem seria refatorar a função recursiva para não depender de referências, a menos que sejam somente leitura.
Como funciona então a recursão dupla?
A resposta de Paul entra em todos os detalhes. Não precisa repeti-la aqui.
Resumidamente
As regras de precedência do C++ não definem se o termo esquerdo ou direito da sua recursão dupla é chamado primeiro. Na verdade, dependendo da ordem escolhida pelo compilador, você pode obter resultados diferentes com o mesmo código.
Demonstração em profundidade
Do seu OP:
Acima está o caso base que ajuda a evitar que a recursão se repita para sempre.
O primeiro termo é call (por suposição). Inicialmente b=7, a=15. Então, como a é imediatamente decrementado na chamada e b é decrementado dentro de F, tanto a quanto b diminuem juntos. Como ab > 2, o caso base atingirá b == 2 antes de a <=0.
Na recursão, o primeiro termo é chamado repetidamente até b == 2. Somente então o 2º termo é chamado e agora a não é decrementado na chamada. Dentro do 2º F, o primeiro F é chamado novamente (por sua suposição). Desta vez, b ainda é 2, pois não é decrementado até depois do caso base. Em seu depurador, certifique-se de observar a Pilha de Chamadas e observe as recursões se desenrolarem.
Um item complicado. O arg a ao chamar o primeiro F é um a menos que o arg a ao chamar o segundo F . Apenas tenha isso em mente.
Fiquei curioso sobre o quão diferentes os resultados podem ser. As variações são controladas por um
a-1sinalizador adicionado,flag_am1.flag_am1= 1: Determinístico com o termo a-1 avaliado primeiro.flag_am1= 0: Determinístico com o termo a-1 avaliado em segundo.flag_am1= -1: Idêntico ao OPflag_am1= -2: Semelhante ao OP, exceto que a ordem das duas funções são trocadas.Observe que para o
flag_am1caso = -2,O importante a lembrar ao analisar os quatro conjuntos de saídas é que, para casos
flag_am1= -1 ou = -2, seus resultados podem variar.Saída:
C++17:
A saída que você postou será gerada somente quando o compilador executar a avaliação da subexpressão
F(v, a - 1, b)antesF(v, a, b)de cada avaliação da expressãoF(v, a - 1, b) + F(v, a, b).Uma verificação rápida que você pode fazer trocando os operandos (subexpressão) -
F(v, a, b) + F(v, a - 1, b). Com isso, você pode obter uma saída diferente.O rastreamento de chamada recursiva para a expressão dada será como uma árvore binária, mas há um porém aqui - o parâmetro
bda funçãoF()é uma referência. O que significa que qualquer mudança no valorbrefletirá em todos os lugares para onde foi referenciado.Para o valor fornecido do parâmetro
aandb(a = 15eb = 7), uma vez que o valor debse tornará2, a condiçãob <= 2será satisfeita e o restante das chamadas recursivas paraF()a função simplesmente retornarão o valor dea(o que quer que seja passado como argumento naquela chamada para a funçãoF()).Suponha que, em cada chamada para a função
F(), ao avaliar a expressão expressionF(v, a - 1, b) + F(v, a, b), o compilador avalie a subexpressãoF(v, a - 1, b)primeiro. É assim que a árvore de recursão será:Portanto, a saída que você está obtendo: