What is the best way to detect that a recursive function is called by another function, not by function itself?

Question

Suppose I have a recursive function rec_fun() and it have two block of code, block_1 and block_n. block_1 must execute only once when rec_fun() is initially called by another function like main() and block_n must execute every time rec_fun() is called, whether by another function or by function itself.

rec_fun()
{
   {
      ...
      //block_1
      //must be executed on first call only
      ...
   }

   {
      ...
      //block_n
      //with recursive call and exit condition
      ...
   }
}

What is the best way to achieve this? I have thought few ways like using a counter i as parameter to rec_fun() initially passed with 0 and incrementing it in subsequent call, so that the function can determine whether it is first call or not. Another approach is to put block_n in another helper function and call it from rec_fun(). But in first approach I have to pass an unnecessary argument 0 and second approach creates an unnecessary function. What is the best way to accomplish this, according to you?

I'll appreciate if you provide some useful links to learn recursion.

Answer 1

The C language does not give the function any information regarding its caller so there is no portable way to test whether rec_fun() was called from another function or recursively from itself.

Your goal can be achieved by passing an extra argument to the function with a different value for outsider and recursive calls. This is cumbersome and error prone.

The standard approach for your problem is to use an ancillary function rec_fun1(): the main function rec_fun() is called from other functions and the recursive ancillary function is called from rec_fun() and recursively from rec_fun1() itself.

A classic example of this is mergesort() which would allocate the temporary work array and call a recursive mergesort1() that uses the temporary array to perform the top down merge sort algorithm. Upon return from the call to mergesort1(), mergesort() frees the temporary array and returns to the caller.

Answer 2

You can pass a parameter that you change as you move down the recursion and make block 1 ran based on the condition of the parameter. If you use an if/else if for block 1 and 2 then you're good.

your_func(the_param){
    if(the_param) {
        // the code that only runs on the first call
        }
    else if(the_param) {
        // the code that runs every other call
        }

Answer 3

You can use static variable as counter.

rec_fun()
{
   static int i = 0;

   if (++i == 1) {
      ...
      //block_1
      //must be executed on first call only
      ...
   }

   {
      ...
      //block_n
      //with recursive call and exit condition
      ...
   }

   --i; // internal house keeping to track whether internal, or external caller 
}

Answer 4

I will go against your intuition completely and will suggest to combine the two approaches you consider inappropriate. Because they are appropriate. I will create a recursive implementation with extra parameter, but for convenience and "hiding" I will also make a wrapper function:

void rec_func(bool init) 
{
    if (init) {
        /* initialization logoc */
    }
    /* common recursive code */
    rec_func(false);

}

void wrapper_func(void)
{
    rec_func(true);
}

Note, nothing is "unnecessary" here. The extra parameter helps to keep the function logic in one unit. The wrapper function helps the caller not to mess with unrelated parameters.

Answer 5

Your second solution is usually the correct one.

The second function isn't any less necessary than any other function. You have one function that defines what is needed to implement whatever it is that the external caller expects your code to do. You have another to define whatever it is that you're going to do recursively.

Those apparently do different things and meet different requirements. As such, it's entirely appropriate that they be implemented in different functions.

It's possible to combine these into a single function that varies its behavior depending on a parameter that's passed. If the difference in behavior is small enough, this can be a somewhat reasonable approach--but I would say having one function do two different sorts of things is generally a kludge. The only question is whether it's a small enough kludge that you choose to overlook its being kludgy, or a big enough one that you shouldn't overlook it.

As so ensuring that the second function isn't accidentally called by some "outsider", the usual is to make it a static function, so you'd have a structure on this general order:

foo.h

#pragma once
int foo(int);

foo.c

typedef result_t /* whatever */;

static result_t blocka(int) {
    // stuff for block a
}

static int blockb(result_t const *) {
    // stuff for block b
}

int foo(int input) {
   result_t internal_result = blocka(input);
   return blockb(&internal_result);
}

In this case, I've written both blocka and blockb as separate "unnecessary" functions. Since I don't know what either your block a or block b does, it's hard to guess whether that's justified or not. But I would not start by thinking in terms of whether a function is necessary. Rather the opposite, for almost any block of code with a reasonably well defined interface and functionality, writing a function to embody that block of code should be more or less the default.

For example, if you have an if/then/else kind of situation:

if (foo) {
    // do foo stuff
} else {
    // do not-foo stuff
}

Think about/ask yourself whether you can give a meaningful name to the "do foo stuff" block and/or the "do not-foo stuff" blocks. That is, can you give a name to what they're doing?

If so, there's a reasonable chance that they should be implemented as functions, and then your if/then/else block can become a more readable, higher-level guide to what's going on:

if (data_sorted(input))
    process_sorted_data(input);
else
    process_random_data(input);

Moving these blocks of code into (reasonably well-named) functions makes it much easier for a reader to understand the intent behind the code, rather than having to divine your intent from the content.

Answer 6

Hide it behind a layer of indirection:

func()
{
   //block_1
   // compute what you need  
   // and pass it to rec_fun either as value, or as a pointer

   rec_func(&block_1_result);
}

And make sure you expose only func for your users.

and second approach creates an unnecessary function

So? Unless you are in an extremely limited environment like an embedded device with very limited memory that's really not an issue. And the function is not "unnecessary". It's unnecessary if you think the user doesn't need 2 functions, but it's necessary if you think from the implementation view: it's needed by the implementation (actually it's one solution, but still the argument holds).