Explanation of recursive functioning

Question

I’m at the beginning of system analysis studies and I’m learning programming language. In C language studies I started to see recursiveness and some codes that have recursiveness I get lost and end up not understanding. I’m having doubts 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 the entire 5, my result will be -14? I’m not getting what the return (func(n-1)-n) ago.

Answer 1

And iterative 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);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

I wrote the iterative code in a way that’s not ideal just for easier visualization. And I wrote how you usually write the functional code in one line.

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

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

So call it:

func(5) flame func(4) - 5 what call func(3) - 4 what call func(2) - 3 what call func(1) - 2 what call func(0) - 1 and then how func() receives 0 he falls in the other condition and returns 1 without calling anything else. Note that it will form a function call stack (the term officially used is this same).

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

My suggestion to better understand is to see running, put this code to run in an IDE, turn on a breakpoint, Stop at the first line and go running step by step, and see how everything is called, how the values are changing. There is no better way to understand the functioning of the computer in the algorithm that is trying to identify what it does.

Answer 2

The main question would be "what your function wants to do?". What it does is decrease the number typed 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

Analyzing this, we would have at the end the operation 1 - 1 - 2 - 3 - 4 - 5, which results in -14.

The easiest way to understand is to understand what I’ve put down as main question; Once this is done, you can formulate a logic and train recursiveness so that it doesn’t catch on..

---

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