Função recursiva

[kodiak]

Olá pessoal.

Tenho o seguinte programa em C

#include <stdio.h>
#include <stdlib.h>


int func(int n0, int n);

int main ()
{
int n0=2, n=4, nFinal=0;
nFinal = func(n0, n);
printf ("%d\n", nFinal);
return 0;
}
int func(int n0, int n){
    if (n > 1){
        int nFinal = func(n0, --n);
        return (nFinal*nFinal) + n0;
    }
    return n0;
}

Para compreender melhor a parte da recursividade, coloquei uns prints na função.

int func(int n0, int n){
    if (n > 1){
        printf("%d----\n",n);
        int nFinal = func(n0, --n);
        printf("#####\n");
        printf("----%d\n",nFinal);
        return (nFinal*nFinal) + n0;
        
    }
    return n0;
}

Correndo o código, o output é o seguinte:

4----

3----

2----

#####

----2

#####

----6

#####

----38

1446

E é aqui que entram as minhas dúvidas.

Quando o programa entra em int nFinal = func(n0, --n); eu compreendo que ele volta a chamar a função com o n0 = 2 e a cada iteração  vai decrementado o n e daí vem que a cada passagem ele imprima

4----

3----

2----

Compreendo que ele pára assim que faz o controlo no if para saber se o n > 1 e como o n é <= 1 ele faz o return n0, ou seja, o nFinal fica a 0. Aí passa para a linha seguinte e faz o return (nFinal*nFinal) + n0; que neste caso é (0*0) + 2

A minha dúvida é aqui. O programa não devia finalizar aqui? Ou quando ele faz return (nFinal*nFinal) + n0; ele volta a chamar a função recursiva? É que não faz sentido porque os prints que faço do n apenas são impressos na primeira passagem.

Alguém pode esclarecer-me?

Obrigado,

kodiak

[KTachyon]

Quando ele retorna está a voltar a um outro scope da mesma função. A função chamada é sempre a mesma, mas para cada chamada é criado um scope novo que pode ter diferentes valores.

Normalmente, tudo o que está entre {} é um scope novo, logo quando fazes uma chamada à função é como se estivesses a entrar num novo bloco {}. O anterior não deixa de existir. Por exemplo:

int main() {
    int n = 0;
    
    {
        int n = 1;
        printf("%d\n", n);
    }
    
    printf("%d\n", n);

    return 0;
}

Tens uma declaração da variável n no main, inicializada a zero. Depois crias um scope novo em que inicializas uma nova variável n a 1. Nesse scope a variável tem o valor 1, mas quando retornas ao scope do main, a variável n já tem o valor zero.

No caso da recursividade, podes imaginar como tendo vários scopes dentro de scopes:

{
    // chamada
    {
        // chamada resursiva 1
        {
            // chamada resursiva 2
            {
                // chamada resursiva 3
            }
        }
    }
}

[kodiak]

Olá KTachyon.

Obrigado pela explicação. Gostava de dizer que compreendi mas continuo a não entender 😕

[HappyHippyHippo]

tenta ver assim :

int func(int n0, int n){
    if (n > 1){
        int nFinal = {
           int n0_1 = n0, n_1 = --n;
           if (n_1 > 1) {
               int n0_2 = n0, n_2 = --n_1;
               if (n_2 > 1) {
                  ... // por ai adiante
                  int nFinal = (nFinal*nFinal) + n0;
               } else
                  nFinal = n0;
             }
             nFinal = (nFinal*nFinal) + n0;
           } else
               nFinal = n0;
       }
       return (nFinal*nFinal) + n0;
    }
    return n0;
}

ou melhor para perceber:

int func1(int n0, int n){
    if (n > 1){
        int nFinal = func2(n0, --n);
        return (nFinal*nFinal) + n0;
    }
    return n0;
}
int func2(int n0, int n){
    if (n > 1){
        int nFinal = func3(n0, --n);
        return (nFinal*nFinal) + n0;
    }
    return n0;
}
int func3(int n0, int n){
    if (n > 1){
        int nFinal = ... // por ai a diante
        return (nFinal*nFinal) + n0;
    }
    return n0;
}

[pikax]

basicamente o "return

A minha dúvida é aqui. O programa não devia finalizar aqui? Ou quando ele faz return (nFinal*nFinal) + n0; ele volta a chamar a função recursiva? É que não faz sentido porque os prints que faço do n apenas são impressos na primeira passagem.

uma funcao recursiva chama-se a si mesma e quando chama, tem que esperar que a funcao que chamou termine, e' por isso que os teus primeiros printf sao imprimidos(printf("%d----\n",n) ; ), depois o seguintes serao imprimidos da ultima funcao chamada, para a primeira.

um exemplo facil de perceber e' imprimir um ciclo com uma funcao recursiva, ou o factorial:

#include<stdio.h>

int print_ciclo(int i,int total)
{
    if(i>=total)
        return 0;

    printf("%d\n",i);
    return print_ciclo(++i,total);
}

int factorial(int numero)
{
    if(numero<1)
        return 1;
    return numero * factorial(numero-1);
}

int main()
{
    int num;print_ciclo
    int i;
    int totalciclo;

    printf("Criar um ciclo de...ate'(ex:0 10):");
    scanf("%d %d",&i,&totalciclo);
    print_ciclo(i,totalciclo);

    printf("\n\nInsira um numero para saber o factorial:");
    scanf("%d",&num);
    printf("\nfactorial de %d e' %d",num,factorial(num));

    return 0;
}

[kodiak]

Obrigado HappyHippyHippo.

Está mais claro com os exemplos que deste mas continuo com  uma dúvida.

Imagina que coloco mais um print:

int func(int n0, int n){
    if (n > 1){
        printf("%d----\n",n);
        int nFinal = func(n0, --n);
        printf("#####\n");
        printf("----%d\n",nFinal);
        return (nFinal*nFinal) + n0;

    }
    printf("teste\n");
    return n0;
}

O output é o seguinte

4----
3----
2----
teste
#####
----2
#####
----6
#####
----38
nFinal ao fim de 4 iteracoes e 1446:

Ou seja, ele acaba por imprimir aquele teste mas o resultado que ele vai devolver à função é o que está no topo da pilha?

[pikax]

Ou seja, ele acaba por imprimir aquele teste mas o resultado que ele vai devolver à função é o que está no topo da pilha?

Quando chamas a funcao dentro da funcao, vias decrementar o n(--n); quer dizer que quando o n<=1 e' na ultima vez que a funcao ira ser chamada.

Tenta fazer os passos que o programa faz num papel, sera melhor

[HappyHippyHippo]

verifica que somente na ultima chamada da função func é que o if falha e é retornado n0

depois de retornar o n0, vai guardar esse valor na variável nFinal da penúltima chamada da função func, retornando agora a conta feita.

este valor é retornado à antepenúltima chamada da função func ....

assim por diante até voltar à primeira chamada.

é por essa razão que printf("teste") aparece lá pelo meio.

[kodiak]

Ok.

Obrigado a todos pela ajuda.

Acho que já está compreendido 😕