Vamos considerar o trecho de código que você colocou na pergunta, apenas atribuindo o retorno da chamada a uma variável, para simplificar a explicação:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
resultado = fibonacci(5)
A memória no computador possui um endereço e um valor. Para fins didáticos, vamos supor que esta memória seja sequencial, iniciando no endereço 0x01 e que possui uma etiqueta, referente ao nome da variável:

O programa irá executar a última linha do código, reservando um espaço na memória para a variável e definido o retorno da função como sendo seu valor:
resultado = fibonacci(5)
Na memória fica:

Passo 1
Para saber qual valor de fibonacci(5)
, a função fibonacci
é executada:
- A função
fibonacci
é chamada com parâmetro n = 5
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(4) + fibonacci(3)
;
Ou seja, o valor de fibonacci(5)
será fibonacci(4) + fibonacci(3)
. Então na memória, ficaria:

Passo 2
Então, o programa irá tentar primeiro calcular o valor de fibonacci(4)
, pois a expressão é analisada da esquerda para a direita:
- A função
fibonacci
é chamada com parâmetro n = 4
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(3) + fibonacci(2)
;
Ou seja, o valor de fibonacci(4)
será fibonacci(3) + fibonacci(2)
. Então na memória, ficaria:

Passo 3
Então, para saber o valor de fibonacci(4)
, o programa precisa saber o valor de fibonacci(3)
e fibonacci(2)
. Analisando da esquerda para a direita, primeiro é calculado fibonacci(3)
:
- A função
fibonacci
é chamada com parâmetro n = 3
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(2) + fibonacci(1)
;
Ou seja, o valor de fibonacci(3)
será fibonacci(2) + fibonacci(1)
. Então na memória, ficaria:

Passo 4
A mesma lógica: para saber o valor de fibonacci(3)
, antes é necessário saber o valor de fibonacci(2)
e fibonacci(1)
. Da esquerda para a direita, calcula-se o valor de fibonacci(2)
:
- A função
fibonacci
é chamada com parâmetro n = 2
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(1) + fibonacci(0)
;
Ou seja, o valor de fibonacci(2)
será fibonacci(1) + fibonacci(0)
. Então na memória, ficaria:

Passo 5
Para calcular o valor de fibonacci(2)
então é preciso de fibonacci(1)
e fibonacci(0)
. Da esquerda para a direita, calcula-se primeiro fibonacci(1)
:
- A função
fibonacci
é chamada com parâmetro n = 1
;
- Verifica-se se
n
é menor ou igual a 1. Verdadeiro;
- Retorne o valor de
n
(1);
Neste ponto, a recusividade é interrompida brevemente, pois o valor não depende mais de uma outra chamada da função. Assim, na memória fica:

Passo 6
Assim, tendo o valor de fibonacci(1)
, este é substituído em fibonacci(2)
:

Passo 7
Mas ainda é necessário calcular o valor de fibonacci(0)
:
- A função
fibonacci
é chamada com parâmetro n = 0
;
- Verifica-se se
n
é menor ou igual a 1. Verdadeiro;
- Retorne o valor de
n
(0);
Então na memória fica:

Passo 8
Este valor é prontamente substituído no valor de fibonacci(2)
:

Passo 9
O valor de fibonacci(2)
é obtido somando 1+0 = 1 e é substituído em fibonacci(3)
:

Passo 10
Para calcular o valor final de fibonacci(3)
é preciso o valor de fibonacci(1)
novamente, então é feito novamente a chamada:
- A função
fibonacci
é chamada com parâmetro n = 1
;
- Verifica-se se
n
é menor ou igual a 1. Verdadeiro;
- Retorne o valor de
n
(1);
Ficando na memória:

Passo 11
Este valor é prontamente substituído em fibonacci(3)
, ficando:

Passo 12
O valor de fibonacci(3)
então valerá 1+1 = 2, sendo substituído em fibonacci(4)
:

Passo 13
Mas novamente é preciso o valor de fibonacci(2)
, então:
- A função
fibonacci
é chamada com parâmetro n = 2
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(1) + fibonacci(0)
;
Ficando na memória:

Passo 14
Já sabemos que fibonacci(1)
retornará 1 e fibonacci(0)
retornará 0, então para simplificar, colocarei direto seus valores em fibonacci(2)
:

Passo 15
Ficando o valor de fibonacci(2)
igual a 1+0 = 1, sendo prontamente substituído em fibonacci(4)
:

Passo 16
Assim, o valor de fibonacci(4)
ficará igual à 2+1 = 3, sendo prontamente substituído em fibonacci(5)
:

Passo 17
Para calcular ainda o valor final de fibonacci(5)
é necessário o valor de fibonacci(3)
:
- A função
fibonacci
é chamada com parâmetro n = 3
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(2) + fibonacci(1)
;
Ou seja, o valor de fibonacci(3)
será fibonacci(2) + fibonacci(1)
:

Passo 18
Analisando da esquerda para a direita, novamente calcula-se o valor de fibonacci(2)
:
- A função
fibonacci
é chamada com parâmetro n = 2
;
- Verifica-se se
n
é menor ou igual a 1. Falso, executa o else
;
- Retorne o valor de
fibonacci(1) + fibonacci(0)
;
Ficando na memória:

Passo 19
Como já sabemos, fibonacci(1)
vale 1 e fibonacci(0)
vale 0, então substituindo os valores:

Passo 20
Resultando em fibonacci(2)
igual a 1+0 = 1, sendo prontamente substituído em fibonacci(3)
:

Passo 21
Falta ainda calcular o valor de fibonacci(1)
, que já sabemos que vale 1:

Passo 22
Assim, o valor de fibonacci(3)
será 1+1 = 2, sendo prontamente substituído em fibonacci(5)
:

Passo 23
Finalmente, o valor de fibonacci(5)
valerá 3+2 = 5, sendo substituído prontamente em resultado
:

Portanto, quando for executado:
resultado = fibonacci(5)
O valor de resultado
será 5. Valor este que pode ser comprovado executando o código.
Veja funcionando no Ideone.