Can Recursion be named as a simple function call?

Question

Please consider an Recursive function :

 1)   int calc(int num)
       {

 2)    sum=sum+num;//sum is a global variable

 3)    num--;

 4)    if(num==0)
 5)    return sum;

 6)    calc(num);

       }

It calculates the sum of an integer . My teacher told me it's not recursion, but a simple function call, because you need to pass num-- as an argument and return calc(num--) .

I was shocked, as I knew only one thing when a function call itself, its recursion.

She also gave the reason, that line no. 2 and 3 is stored extra in stack memory. I have no idea what she was referring to.So after going through stack storage thingy:

enter image description here

Here, I noticed that the function arguments passed are in a recursive way, like n-- in my function. So that they can be linked to the next function call.

For just this sake, can we term it a simple function call instead of recursion?

Storing the data in a global variable is not a good idea. Why don't you just fix it as she suggested? — acfrancis, Nov 08 '13 at 17:58
I have a feeling that this teacher has really no idea as to what he is even talking about... — , Nov 08 '13 at 17:59
It's recursion and it's a special kind of recursion called tail recursion which the compiler will probably compile into a loop. — Charlie Burns, Nov 08 '13 at 17:59
This is a recursive function. It doesn't look like the most typical example, but it is one. — Linuxios, Nov 08 '13 at 17:59
indeed why just not call sum+num. without having globals i mean to declare calc to have to ints as an input and next time u call it to call calc(num+sum ,num--); — user2533527, Nov 08 '13 at 18:03
While in this class, it's not recursion (because the teacher assigned your grade). Once you leave this class, it can be recursion again :) — mah, Nov 08 '13 at 18:03
Well, maybe the teacher means that you don't need recursion here. You need to clarify the terminology with him. If he sees recursion as an implementation detail, then you're not going to be able to identify it by looking at source code, because *anything could be happening under the hood.* To me, recursion is defined as a function calling itself. Plain and simple. — Robert Harvey, Nov 08 '13 at 18:05
and yes your teacher was right about lines 2 and 3 in general she was wrong it is a recursion , but if she would to go through details etc she would be right since this function isn't really good implemented. — user2533527, Nov 08 '13 at 18:05
The function is most certainly recursive, since it calls itself. It's not a _recursive solution to this problem_ though, since it calls itself with the same argument and never approaches the base case. It also seems like it won't return the value that you expect it to since you're not doing `return calc(...);`. Alternatively, if you don't care about returning a value (since `sum` is a global variable, you might as well make this a `void` function. — Joshua Taylor, Nov 08 '13 at 18:10

lurker · Accepted Answer · 2013-11-08T19:00:17.420

4

The teacher has something quite specific in mind even though what you presented is, technically, recursive. Another form which wouldn't depend upon the global would look something like this:

int calc(int num)  // Assume this is valid for non-negative numbers
                   // In that case, type "unsigned int" would be more appropriate
{
    if ( num < 0 )
        return -1;  // Consider this an error; won't happen in recursive case

    if ( num == 0 )
        return 0;

    return num + calc(num-1);
}

edited Nov 08 '13 at 19:00

answered Nov 08 '13 at 18:03

lurker

56,987
9
69
103

You are still using global variable for not good enough reason. – user2533527 Nov 08 '13 at 18:11
@user2533527 What global variable is there here? There's none. There's just `num`, which is an argument of the function. – Joshua Taylor Nov 08 '13 at 18:13
Sorry, you are right :) num sum looks the same ,my bad cheers! Vote goes to you since it is best answer here :) – user2533527 Nov 08 '13 at 18:14
It's worth pointing out that the recursive call here isn't a tail call, which means that it can't (without much more sophisticated compiler acrobatics) be optimized into a loop. – Joshua Taylor Nov 08 '13 at 18:24
when `num <= 0` should it `return 0` ? – joey rohan Nov 08 '13 at 18:57
@joeyrohan it depends upon what you want it to do. I just put it in there for lack of a definition from the OP on what they wanted it to do with negative values. One possibility is to return `-1` as an error (valid only for non-negative integers). I updated it for more appropriate checking. – lurker Nov 08 '13 at 18:59
ohh ya ya got it..my bad! – joey rohan Nov 08 '13 at 18:59
So what I have presented, is a recursion? yes? – joey rohan Nov 08 '13 at 19:22
@joeyrohan yes, indeed, as others have also indicated. It's just not good program structure and not what one would expect as a "tidy" solution to the given problem. – lurker Nov 08 '13 at 19:31

score 2 · Answer 2 · answered Nov 08 '13 at 18:05

You are correct, recursion is a function that calls itself. PERIOD. There are other points worth separately discussing about global variables, and other good programming practices, but whether you implement the decrement operator in the line of code where you call the function recursively or prior to that point, you are still making a recursive call.

score 2 · Answer 3 · edited May 23 '17 at 12:11

It looks like you're trying to calculate, for a given num, the sum of 0 to num. The calc function really just needs one argument, num, and can then call a helper function calc_num which takes the current number and the running sum:

int calc( int num ) {
  return calc_help( num, 0 );
}

Then, calc_help, given a current number, and the sum so far, checks whether num is less than or equal to zero. If it is, then the current running sum is the final sum and can be returned. Otherwise, a recursive call to calc_help is made. The current number for it will be one less than num (so that we're calling calc_help with successively smaller first arguments, getting closer and closer to the case where num <= 0), and the current sum will be sum plus the current number:

int calc_help ( int num, int sum ) {
  return num <= 0 ? sum : calc_help( num-1, sum+num );
}

In a language (like Scheme) that performs tail call optimization, this is essentially the following loop. Some C/C++ compilers do perform tail call optimization (e.g., according to Tail recursion in gcc/g++, GCC will optimize tail calls when -O2 is specified), so this isn't entirely a moot point.

int calc( int num ) {
  int sum = 0;
  while ( num > 0 ) {
    sum = sum+num;
    num = num-1;
  }
  return sum;
}

or (if you want to be a bit more obscure):

int calc( int num ) {
  int sum = 0;
  for ( ; num <= 0; sum+=num, num-- );
  return sum;
}

The more naïve recursive implementation that performs the addition of after the recursive call, i.e.,

int calc( int num ) {
  return num <= 0 ? num : num + calc( num-1 );
}

can't be optimized in this way.

Can Recursion be named as a simple function call?

3 Answers3

Linked