Não tem algo especial nisso, recursão não é um mecanismo mágico cheio de detalhes que você não pode ver. Recursão é só uma função chamar outra função com uma única diferença entre as chamadas mais comuns, a função sendo chamada é a mesma da chamadora, ou pelo menos ocorre uma chamada triangulada.
Não há simultaneidade, primeiro executa uma e depois, na hora dela, executa a outra. Recursão não muda nada na sequência de execução, é exatamente igual qualquer outra chamada de função e execução sequencial.
Na primeira chamada se ele entrar no bloco condicional chamará a função de novo passando o membro indicado ali. Como a função é reentrante ele fará o condicional e se entrar ele porque tem uma um galho ali (não é null
) então ele tem que tentar de novo analisar esse galho da esquerda encontrado, e vai fazendo isso em sequência (sempre olhando o lado esquerdo de cada galho analisado) até que não entre no condicional mais por não ter uma galho à esquerda (agora o valor é null
).
Quando essa função termina sem executar, ele continua o fluxo normal da execução da função, vamos analisá-lo.
Nessa penúltima chamada (a última não entrou no if
) faz uma impressão e depois começa fazer recursão de novo chamando a própria função agora passando o galho da direita, e começa o mesmo processo relatado acima, então se essa nova chamada o valor não for null
ele vai repetindo as chamadas uma por uma nos galhos existentes. Isso encerrará quando for null
e voltará para a chamada anterior.
Depois de terminar isso ele não tem mais qualquer outra linha para executar, então encerra essa função. Mas como ela deve ter sido chamada por ela mesma, ele tem que dar continuidade de onde parou ali.
Faça um teste de mesa com uma árvore montada e veja como fica a execução.
5
/ \
3 8
/ \ / \
1 4 6 10
/ \
9 11
- (nível 1) Chamará onde a
key
é 5 (mas estou antecipando). Ela chama a função passando o necessário.
- (nível 2) Encontra um
left
e chama de novo.
- (nível 3) Agora não tem um
left
, então encerrará (eu acho que esse print(x.key)
deveria estar fora do if
e imprimir 1). A chave é 1. Encerra sem executar.
- (nível 2) Voltando para a chamada anterior agora ele vai chamar com
right
.
- (nível 3) Ele é nulo então executará nada. A chave é 4.
- (nível 2) Voltando ele executa mandado o
right
.
- (nível 2) Agora não tem um objeto, então encerrará. A chave é 3.
- (nível 2) Voltando para a chamada anterior agora ele não tem outro comando a executar.
- (nível 1) Agora voltou e na sequência da função e executa a segunda chamada da função passando o
right
.
- (nível 2) Encontra um
right
e chama de novo.
- Termine você com o lado da direita, ele vai até o nível 4 :)
Pode ser útil escrever um código em linguagem real, pegar um bom software de debug, mandar executar o código com uma árvore real e ver a pilha de chamadas para entender melhor.