Explanation of recursion operation

2

I'm at the beginning of system analysis studies and I'm learning programming language. In C language studies I started to see recursion and some codes that have recursion I get lost and I do not understand. I am doubtful in this simple code:

int func(int n){
    if(n==0){
        return (1);
    } else {
        return (func(n-1)-n);
    }
}

int main(){
    int a,b;
    printf("Digite um valor inteiro: ");
    scanf("%d",&a);
    b=func(a);
    printf("%d\n",b);
    system("PAUSE");
    return 0;
}

Because if I type integer 5, my result will be -14? I'm not understanding what return (func(n-1)-n) does.

    
asked by anonymous 04.12.2018 / 14:28

2 answers

4

The main question would be " what does your job want to do? ". What it does is to decrease the number entered in one and subtract it from the final result, then:

  • func(5) returns the result of func(4) - 5
  • func(4) returns the result of func(3) - 4
  • func(3) returns the result of func(2) - 3
  • func(2) returns the result of func(1) - 2
  • func(1) returns the result of func(0) - 1
  • func(0) returns the result of 1

Looking at this, we would end up with the 1 - 1 - 2 - 3 - 4 - 5 operation, which results in -14 .

The easiest way to understand it is to understand what I have put as the main question ; done that, you can formulate a logic and train recursion to avoid embananar ..

By specifically addressing your question, the return (func(n-1)-n) segment returns to the call; it calls the func() method by passing the n-1 value subtracted from the n value. Being n equal to 12 , return (func(n-1)-n) returns the value returned by call func(11) - 12 .

    
04.12.2018 / 14:36
6

And iterative do you understand?

#include <stdio.h>

int func(int n) {
    return n == 0 ? 1 : func(n - 1) - n;
}

int main() {
    int a;
    printf("Digite um valor inteiro: ");
    scanf("%d", &a);
    printf("%d\n", func(a));
    //agora iterativo
    int n = a;
    int temp = 1;
    while (1) {
        temp -= n; //faz a acumulação na mão
        n--; //faz o n - 1 guardando seu próprio estado
        if (n == 0) break; //condição de saída, poderia estar no próprio while com condição invertida
    }
    printf("%d\n", temp);
}

See running on ideone . And no Coding Ground . Also put it on GitHub for future reference .

I wrote the iterative code in a way that is not ideal just to visualize it easier. And I wrote down how you write the functional code in just one line.

The codes are doing the same thing. Only in an inverted way. In more functional style, which is the recursive you delete a variable because the state is being passed in each function call. In the most imperative style you need the result control variable.

What you are doing in your code and calling the same function one after another passing the value of the variable always subtracting 1, and considering the result always subtracting the value of the moment state, in the case represented by n . In each flame the n will value a value less until it reaches 0, when it considers only to be 1, it is the output condition.

Then call this:

func(5) calls func(4) - 5 calling func(3) - 4 calling func(2) - 3 calling func(1) - 2 calling func(0) - 1 and then func() receiving it falling into the other condition and returning 1 without calling anything else . Note that it will form a stack of function calls (the term officially used is this one).

Then in the return of the call of func(1) - 2 is -1, since func(0) we know that it is 1. And the return of this is -2, and the return of the following is -3, and then returns -4, and finally returns -5. If you accumulate all this it will have -14.

My suggestion to understand better is to see running, put this code to run in an IDE, call a breakpoint , stop in the first line and go running step by step, and see how everything is going called, as the values change. There is no better way to understand how the computer works in the algorithm that is trying to identify what it does.

    
04.12.2018 / 14:45