Primeiramente, segue uma sugestão de leitura que pode ajudar no entendimento de funções de forma geral: O que acontece quando chamamos uma função?.
Dito isso, acho que primeiro podemos ver como seria se a funcao
não fosse recursiva, e depois vemos como a versão recursiva não muda tanto assim. Então vamos modificar um pouco a funcao
para que ela não seja mais recursiva:
int funcao(int a, int b) {
if (b == 0)
return 0;
if (b % 2 == 0) // em vez de chamar "funcao", estou chamando "outra_funcao"
return outra_funcao(a + a, b / 2);
return outra_funcao(a + a, b / 2) + a;
}
int outra_funcao(int a, int b) {
if (b == 0)
return 0;
if (b % 2 == 0)
return outra_funcao(a + a, b / 2);
return outra_funcao(a + a, b / 2) + a;
}
outra_funcao
é praticamente igual à funcao
, com a diferença que a funcao
original não é mais recursiva.
O que acontece quando chamamos funcao(3, 1)
?
Neste caso, a função receberá os valores 3
e 1
, que correspondem aos parâmetros a
e b
. Ou seja, para funcao(3, 1)
, temos que a=3
e b=1
.
Por isso o código não entra no primeiro if
, já que b
não é igual a zero. E como b
é um número ímpar, então b % 2
é 1
, por isso ele também não entra no segundo if
.
Então ele cai no último return
, que é:
return outra_funcao(a + a, b / 2) + a
Ou seja, a funcao
está retornando apenas um valor. Esse valor é o resultado da expressão outra_funcao(a + a, b / 2) + a
. E esta expressão está fazendo basicamente duas coisas:
- chamando
outra_funcao(a + a, b / 2)
- pegando o resultado da chamada acima e somando com
a
O resultado disso tudo é o valor retornado por funcao
. Em nenhum momento tem 2 valores sendo retornados. Temos apenas uma chamada de função (outra_funcao
), cujo resultado é somado com outro valor (no caso, a
), e o resultado dessas operações vira um único valor, que é retornado pela funcao
.
Bom, como chamamos funcao(3, 1)
, temos que a=3
e b=1
, então a expressão acima acaba virando:
return outra_funcao(3 + 3, 1 / 2) + 3
Que por sua vez acaba virando:
return outra_funcao(6, 0) + 3
// como são inteiros, 1 / 2 é "arredondado" para zero
Ou seja, para saber o resultado desta expressão, precisamos saber o valor de outra_funcao(6, 0)
.
E quando chamamos outra_funcao(6, 0)
, temos a=6
e b=0
(esses a
e b
dentro de outra_funcao
não são os mesmos a
e b
da funcao
). Neste caso, entrará no primeiro if
, e por isso ela retorna zero.
Ou seja, return outra_funcao(6, 0) + 3
é o mesmo que return 0 + 3
, que é o mesmo que return 3
. Concluindo, funcao(3, 1)
retorna 3
.
Mas repare que funcao
e outra_funcao
fazem basicamente a mesma coisa. Então para que ter duas funções redundantes, quando eu posso ter uma só?
int funcao(int a, int b) {
if (b == 0)
return 0;
if (b % 2 == 0)
return funcao(a + a, b / 2);
return funcao(a + a, b / 2) + a;
}
Agora funcao
é recursiva (ela é chamada dentro dela mesma). Apesar disso, seu funcionamento continua basicamente o mesmo:
- chamei
funcao(3, 1)
, ou seja, a=3
e b=1
- não entra em nenhum dos
if
's, ou seja, cai no return funcao(a + a, b / 2) + a
- que por sua vez, é o mesmo que
return funcao(3 + 3, 1 / 2) + 3
, que é o mesmo que return funcao(6, 0) + 3
- então agora preciso calcular
funcao(6, 0)
- é outra chamada de função (só porque chamou a mesma funcao
, não muda o fato de ser outra chamada "independente")
- em
funcao(6, 0)
, temos que a=6
e b=0
(como é outra chamada de função, esses a
e b
não são os mesmos da primeira chamada)
- como
b=0
, entra no primeiro if
e retorna zero
- como
funcao(6, 0)
retornou zero, a expressão return funcao(6, 0) + 3
é o mesmo que return 0 + 3
, que é o mesmo que return 3
- ou seja,
funcao(3, 1)
retorna 3
Em nenhum momento há o "retorno de dois valores". A funcao
sempre retorna apenas um valor. O que acontece é que em alguns casos o valor é obtido através de uma expressão que pode envolver outra chamada de função (e não importa se é a mesma função ou outra, a ideia é a mesma: temos que obter o valor retornado pela chamada para poder calcular o resultado final da expressão).
Não existe essa coisa de "escopo de cima", "escopo anterior", nada disso. É apenas uma função que pode chamar outra, que pode chamar outra, que pode chamar outra (sendo que essa "outra" pode ser inclusive a mesma função, com argumentos diferentes). O importante é que todas essas chamadas não fiquem se chamando eternamente, e que em algum momento elas retornem algum valor, que será usado pela chamada anterior, que será usado pela anterior a esta, e assim por diante, até chegar à primeira chamada, que retornará o resultado final.
Outro exemplo: funcao(3, 4)
. Temos que:
a=3
e b=4
, entra no segundo if
, então retorna funcao(a + a, b / 2)
→ funcao(6, 2)
funcao(6, 2)
→ a=6
e b=2
, entra no segundo if
, então retorna funcao(a + a, b / 2)
→ funcao(12, 1)
funcao(12, 1)
→ a=12
e b=1
, não entra em nenhum if
, retorna funcao(a + a, b / 2) + a
→ funcao(24, 0) + 12
funcao(24, 0)
→ a=24
e b=0
, entra no primeiro if
, retorna zero
funcao(12, 1)
retorna funcao(24, 0) + 12
→ 0 + 12
→ 12
funcao(6, 12)
retorna funcao(12, 1)
→ 12
funcao(3, 4)
retorna funcao(6, 2)
→ 12
Ou seja, o resultado é 12.
Outra forma de visualizar:
Se a imagem acima não carregar, segue o mesmo diagrama em ASCII:
+- funcao(3, 4) --------------------------------------------+
| a=3, b=4 |
| entra no segundo if |
| retorna funcao(6, 2) |
| ↓ |
| +- funcao(6, 2) ---------------------------------+ |
| | a=6, b=2 | |
| | entra no segundo if | |
| | retorna funcao(12, 1) | |
| | ↓ | |
| | +- funcao(12, 1) ---------------------+ | |
| | | a=12, b=1 | | |
| | | não entra em nenhum if | | |
| | | retorna funcao(24, 0) + 12 ----+ | | |
| | | ↓ | | | |
| | | +- funcao(24, 0) -------+ | | | |
| | | | a=24, b=0 | | | | |
| | | | entra no primeiro if | | | | |
| | | | retorna zero | | | | |
| | | +---------- | ----------+ | | | |
| | | ↓ | | | |
| | | retorna 0 + 12 ←-----+ | | |
| | | retorna 12 | | |
| | +---------- | ------------------------+ | |
| | | | |
| | retorna 12 ←-----+ | |
| +---------- |------------------------------------+ |
| | |
| retorna 12 ←-----+ |
+-----------------------------------------------------------+
Repetindo: não existe essa história de "escopo de cima", de baixo, anterior, etc. O que temos são chamadas de função. Quando você chama uma função, ela é executada, e só depois que ela retorna, o código que chamou a função continua de onde parou. Quando uma função chama outra (ou ela mesma), ela tem que esperar a chamada terminar, para só depois pegar o resultado retornado e poder usá-lo.
Não tem essa história de "o padrão do C é somar" (como perguntado nos comentários). Foi você que disse que deve fazer uma soma:
funcao(a + a, b / 2) + a
↑
Aqui você disse para somar
Esse código soma o resultado de funcao(a + a, b / 2)
com a
. Só que para fazer esta soma, ele precisa saber o resultado de funcao(a + a, b / 2)
- então ela chama a função novamente para saber qual é esse resultado (só que essa chamada pode acabar fazendo outra chamada, que pode fazer outra, e outra, etc, até que em algum momento elas caem no primeiro if
e começam a retornar os resultados para quem as chamou).
Se em vez dessa soma, tivesse qualquer outra operação (subtração, multiplicação, outra chamada de função, ou qualquer outra expressão válida), ela seria feita. O "padrão" não é somar, é chamar as funções, pegar os resultados e usá-los da forma que o código indica - se o código diz para somar, como é o caso, ele soma.
Enfim, é "só" isso.
return
a execução da função é interrompida e fluxo de processamento é devolvido ao ponto onde a função foi chamada retornando o valor da expressão passado aoreturn
ouvoid
se não nada for passado.return
a função para e é retorna com um valor exatamente no ponto onde a função foi anteriormente chamada. Tudo o que estiver após o return é ignorado.return 0;
retorna zero, aquifuncao(a+a, b/2);
retorna o resultado da função e aquireturn funcao(a+a, b/2)+a;
retorna o resultado da função maisa
.