Programa recursivo inverte a execução?

O que queres dizer com “inverte a execução”? O primeiro decParaBin que vai ser completado é o de 1, sim, mas isso não quer dizer que esse foi o primeiro a ser iniciado. A execução é efetuado “normalmente” de cima para baixo, mas fica, como dizes no teu exemplo, à espera de outras chamadas para completar.

Experimenta colocar logs, talvez ajude:

public static String decParaBin(int n) {
        System.out.println("Chamada: decParaBin(" + n + ")");

        // Caso base: se o número for 0 ou 1, retorna o próprio número.
        if (n <= 1) {
            System.out.println("→ Caso base atingido com n = " + n + ", retorna: " + n);
            return Integer.toString(n);
        } else {
            int resto = n % 2;
            int quociente = n / 2;
            System.out.println("→ n = " + n + ", quociente = " + quociente + ", resto = " + resto);
            
            String resultadoParcial = decParaBin(quociente);
            System.out.println("← Recebido " + resultadoParcial + " que vou juntar ao resto " + resto);
            String resultadoFinal = resultadoParcial + resto;

            System.out.println("← Retorno de decParaBin(" + n + "): " + resultadoFinal);
            return resultadoFinal;
        }
    }

Ouput:

Chamada: decParaBin(14)
→ n = 14, quociente = 7, resto = 0
Chamada: decParaBin(7)
→ n = 7, quociente = 3, resto = 1
Chamada: decParaBin(3)
→ n = 3, quociente = 1, resto = 1
Chamada: decParaBin(1)
→ Caso base atingido com n = 1, retorna: 1
← Recebido 1 que vou juntar ao resto 1
← Retorno de decParaBin(3): 11
← Recebido 11 que vou juntar ao resto 1
← Retorno de decParaBin(7): 111
← Recebido 111 que vou juntar ao resto 0
← Retorno de decParaBin(14): 1110

Não, ele “inverte” porque o código diz que é pra fazer assim.

Por exemplo, ao fazer decParaBin(7) + (14 % 2), ele precisa concatenar duas coisas:

• o resultado de decParaBin(7)
• o resultado de 14 % 2

O primeiro é uma chamada recursiva, então ele vai fazendo as outras chamadas (decParaBin(3) + (7 % 2), etc), e no final ele pega esse resultado e concatena com o resultado de 14 % 2 (que é zero). Por isso que o zero fica no final.

É assim:

• decParaBin(14): retorna o resultado de decParaBin(7) concatenado com o resultado de 14 % 2
  • decParaBin(7): retorna o resultado de decParaBin(3) concatenado com o resultado de 7 % 2
    • decParaBin(3): retorna o resultado de decParaBin(1) concatenado com o resultado de 3 % 2
      • decParaBin(1): retorna 1 (caso base)
    • decParaBin(3): o resultado de decParaBin(1) é 1, concatenado com o resultado de 3 % 2 (que é 1), retorna 11
  • decParaBin(7): o resultado de decParaBin(3) é 11, concatenado com o resultado de 7 % 2 (que é 1), retorna 111
• decParaBin(14): o resultado de decParaBin(7) é 111, concatenado com o resultado de 14 % 2 (que é 0), retorna 1110

Talvez assim fique mais fácil visualizar:

┏━ decParaBin(14) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃  retorna decParaBin(7) + (14 % 2) ──────────────────────╮  ┃
┃            ↓                                            │  ┃
┃   ┏━ decParaBin(7) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓  │  ┃
┃   ┃  retorna decParaBin(3) + (7 % 2) ─────────────╮  ┃  │  ┃
┃   ┃            ↓                                  │  ┃  │  ┃
┃   ┃   ┏━ decParaBin(3) ━━━━━━━━━━━━━━━━━━━━━━━┓   │  ┃  │  ┃
┃   ┃   ┃  retorna decParaBin(1) + (3 % 2) ──╮  ┃   │  ┃  │  ┃
┃   ┃   ┃            ↓                       │  ┃   │  ┃  │  ┃
┃   ┃   ┃   ┏━ decParaBin(1) ━━━━━━━┓        │  ┃   │  ┃  │  ┃
┃   ┃   ┃   ┃  retorna  1           ┃        │  ┃   │  ┃  │  ┃
┃   ┃   ┃   ┗━━━━━━━━━━ │ ━━━━━━━━━━┛        │  ┃   │  ┃  │  ┃
┃   ┃   ┃               ↓                    │  ┃   │  ┃  │  ┃
┃   ┃   ┃  retorna      1  +  1  ←───────────╯  ┃   │  ┃  │  ┃
┃   ┃   ┃  retorna      11                      ┃   │  ┃  │  ┃
┃   ┃   ┗━━━━━━━━━━━━━━ │ ━━━━━━━━━━━━━━━━━━━━━━┛   │  ┃  │  ┃
┃   ┃                   ↓                           │  ┃  │  ┃
┃   ┃   retorna         11 + 1  ←───────────────────╯  ┃  │  ┃
┃   ┃   retorna         111                            ┃  │  ┃
┃   ┗━━━━━━━━━━━━━━━━━━ │ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛  │  ┃
┃                       ↓                                 │  ┃
┃   retorna            111 + 0  ←─────────────────────────╯  ┃
┃   retorna            1110                                  ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

O mesmo diagrama como imagem:

Diagrama de chamadas recursivas902×902 41.1 KB

Entendi. Mas já vi também que a chamada recursiva inverte né. Como que se escreve por exemplo 13 em binário 1101 é de cima para baixo da esquerda para a direita? Outro exemplo é o 11 em binário 1011

Não tem essa de “inverter”. As expressões são concatenadas na ordem que o código indicou. No caso:

return decParaBin(n / 2) + (n % 2);

Aqui o código pega o resultado de decParaBin(n / 2) e concatena com o resultado de n % 2. Não teve inversão de nada, o n % 2 ficou no final porque a expressão diz que ele fica no final.

Mas para concatenar, ele precisa primeiro saber o resultado de decParaBin(n / 2). E para isso ele faz a chamada recursiva.

De forma bem resumida, ao encontrar a expressão decParaBin(n / 2) + (n % 2), ele verifica que o operador + possui dois operandos:

1. o resultado de decParaBin(n / 2)
2. o resultado de (n % 2)

Como decParaBin retorna uma string, então o operador + significa “concatenar”. Mas para concatenar, primeiro ele precisa saber o valor de cada operando.

No caso do primeiro (decParaBin(n / 2)), ele precisa fazer uma chamada recursiva.

No caso de (n % 2), basta fazer o cálculo.

Depois que a chamada recursiva retorna, ele concatena (colocando decParaBin(n / 2) primeiro, e (n % 2) depois). Ninguém “inverteu” nada, ele colocou as coisas na ordem que o código indicou. Se o código dissesse para, por exemplo, colocar (n % 2) no começo, ele colocaria.

Acho que não entendi a pergunta. 13 em binário é 1101, e pronto. Como assim “de cima para baixo”?

Acho que a dificuldade de entendimento do PO está no fato de ser uma recursão à esquerda, montando a representação binária da direita para a esquerda. Talvez se ele começar a estudar por algum exemplo mais simples, como o clássico fatorial, fique mais fácil de entender o que está acontecendo.