Recursion - Not Returning Values as Expected

Question

I'm currently writing a program to return all additions to a number subtracted from itself (For example, if 3 were the number, the output should be 6 (3+2+1). Essentially, I'm trying to have the function return the permutation of a number, but with addition, instead of mulitplication. This seemed like a perfect situation for a recursive function (something I struggling to understand). In my function, I would expect that the return value is not relevant (during the while loop) as the information is directly contained in the variables (specifically, static b). Yet, when I change the while loop in my function, to anything other than b, the wrong value gets returned from the function, into main() - it's always 0. What's even more confusing is that when I do a printf of b, right before the return of the (second - outside of while loop) b return value, my function prints the correct value (regardless of the return value above). Why must my function return b in the while loop (first return function) for the function to return the correct value, which is 55 (10+9+8+7+6+5+4+3+2+1+0)?

As the code is below, it works correctly.

#include <stdlib.h>
#include <stdio.h>
    
int sumyears(int a)
{
    static int b=0;
    while(a>0)
    {
        b+=a;
        sumyears(a-1);
        return b;  //Program works correctly when I return b, but not when I return any other value, including a
    }
    printf("%d", b); //Program will always print correct value, but return different values based upon the return value in the while loop
    return b;
}
    
int main()
{
    printf("%d", sumyears(10));
}

Answer 1

seemed like a perfect situation for a recursive function (something I struggling to understand)

You want to compute the sum of all integers up to n.

• If n == 0, then the sum is obviously 0

• Otherwise:

  (0 + 1 + ... + n) = (0 + 1 + ... + (n - 1)) + n
  
   sumOfIntsUpTo(n) =   sumOfIntsUpTo(n - 1)  + n
  

As a recursive function:

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

int sumIntsUpTo(int a) {
  return (a <= 0) ? 0 : (sumIntsUpTo(a - 1) + a);
}
int main() {
  printf("%d", sumIntsUpTo(10));
}

There is of course a well known explicit formula for that.

I don't know where you got the idea of using static inside of recursive functions, but I'd suggest to discard this source (delete the link / burn the book / don't talk to the weird person who suggested that). When you're trying to write down a recursive definition, the absolutely last thing that you want to deal with is some global mutable state accessed by each invocation of this function (unless you're generating names... and a couple of other valid use cases that you shouldn't worry about for now).

Answer 2

Understanding Recursion with and without Static Variables

Recursion works like a stack, where each recursive call creates a new stack frame. In this explanation, we'll look at two approaches to understanding recursion—one using a static variable and one without.

Approach 1: Without Static Variables

Consider the following recursive method that calculates the sum of integers from a down to 1:

public int doSum(int a) {
    if (a == 1) {
        return 1;
    }
    int result = a + doSum(a - 1);
    return result;
}

Let's trace the execution with a = 3:

1. Initial Call: doSum(3)

result = 3 + doSum(2)

2. Recursive Call: doSum(2)

result = 2 + doSum(1)

3. Base Case: doSum(1)

Returns 1

4. Back to doSum(2)

result = 2 + 1

Returns 3

5. Back to doSum(3)

result = 3 + 3

Returns 6

The key idea here is that each recursive call returns a value that is used in the previous call. Each function call has its own separate instance of local variables (result in this case).

Approach 2: With Static Variables

In this approach, we'll use a static variable to accumulate the sum:

static int b = 0;

public void accumulateSum(int a) {
    if (a == 0) {
        return;
    }
    b = b + a;
    accumulateSum(a - 1);
}

Tracing the execution with a = 2:

1. Initial Call: accumulateSum(2)

b = 0 + 2

Recursive Call: accumulateSum(1)

2. Recursive Call: accumulateSum(1)

b = 2 + 1

Recursive Call: accumulateSum(0)

3. Base Case: accumulateSum(0)

Returns (No change to b)

After execution, b will hold the accumulated sum of 2 + 1, which is 3.

Key Differences

Non-static Variables: Each recursive call has its own separate instance of the local variables. Values must be returned and passed through the recursion chain.

Static Variables: The variable is shared across all recursive calls. Its value is updated globally, so it retains changes across different calls.

Understanding both approaches is crucial. Non-static recursion relies on passing and returning values, while static recursion directly modifies a shared state.