Recursive a+b function

Question

I am practising recursion and have written the small code for summing a+b as below:

#include <stdio.h>

int b=6;
static int cnt;

void main(void)
{
    int a=9,sum;


    sum=succ(a);

    printf("Sum returned : %d\n",sum);
}

int succ(x)
{
    cnt++;
    return(cnt<=b ? succ(x+1) : x++);
}

I am getting the results fine using this. Can anyone suggest optimization or better code for this? I also want to understand how stacking happens in this case for variables cnt and x. Are they stacking in pairs like 0-9, 1-10 ,2-11,3-12 ,4-13, then at last when cnt is 5 it return x from the post-increment return?

Answer 1

First of all, main should be declared int main.

Second, I would advise passing the cnt (which I have called iteration_number) as a parameter as well. Also, you should avoid using a global (b). If you define a helper function, that won't change the signature of your function:

int add_helper(int value, int max, int iteration_number)
{
    if (iteration_number >= max) return value;

    return add_helper(value + 1, max, iteration_number + 1);
}

int add(int a, int b)
{
    add_helper(a, b, 0);
}

Note that I have refactored your b to be a parameter, which I have called max. The function can be used like this:

int main(void)
{
    int start = 9; // Your a
    int count = 6; // Your b

    int sum = succ(start, count);
}

(If you are using C89 instead of C99 or C11, there should be a return 0; at the end of main()).

---

However, the "good" way to define addition recursively is by increasing one number and decreasing the other:

int add(int a, int b)
{
    if (b == 0) return a;

    return add(a + 1, b - 1);
}

Modifying the function to work with negative numbers is left as an exercise to the reader.

(Note: Normally you want to subtract from the lowest number and add to the largest. I left that out to keep the example compact.)

---

I also want to understand how stacking happens in this case for variables cnt and x.

By "stacking", I assume you mean how the variables are pushed onto the stack as the function is called. Your cnt has static linkage, and is not pushed onto the stack at all. In my example, value, max and iteration_number will be pushed onto the stack for each call. (Exactly how is, as far as I know, implementation defined and depends on the calling convention in use.) In other words, assuming no optimization, the arguments will take iteration_number * sizeof(int) bytes on the stack.

If you want to keep track of the values, simply print them in the recursive function like this:

int succ_helper(int value, int max, int iteration_number)
{
    if (iteration_number >= max) return value;

    printf("%d: %d - %d\n", iteration_number, value, max);

    return succ_helper(value + 1, max, iteration_number + 1);
}

---

Can anyone suggest optimization or better code for this?

int sum = 9 + 6;

:-)

Answer 2

"I also want to understand how stacking happens in this case for variables cnt and x. Are they stacking in pairs like 0-9, 1-10 ,2-11,3-12 ,4-13"

No, the value from cnt is not on the stack at all. It's global, so it will change along with the recursive execution.

"then at last when cnt is 5 it return x from the post-increment return?"

Well, yes it will return the value of x, but the post-increment is pointless as the variable is never used with the incremented value.

By using global variables in the recursive code, it's not using recursion properly. It still works as long as you only have a single branch of recursion, but for a more complex task the branches would mess with each others values.

To use recursion properly, you need to send all the data into the function that it needs:

void main(void) {
  int a = 9, sum, b = 6;

  sum = succ(a, b, 0);

  printf("Sum returned : %d\n",sum);
}

int succ(int x, int y, int cnt) {
  return cnt < y ? succ(x + 1, y, cnt + 1) : x;
}

However, this is not really a good example of how recursion works. Normally a recursive function would divide the work into smaller parts that would each be executed recursively, instead of shaving off a single piece of work and do the rest of the work recursively. A recursive algorithm shouldn't go deeper than perhaps 10 or 20 levels. When you use recursion to just do looping, as in the example, it's inefficient and you will easily run into a stack overflow for larger values.