Is there any clever trick that can make recursions go deeper?

Question

This is a program that prints infinite numbers.

#define false 0
#define true 1

int test(int idx) {
  printf("%d\n",idx);
  test(idx+1);
  return 0;
}

int main() {
  test(0);
  return 0;
}
// Segmentation fault: 11

This program ended with a segfault after printing 262045. I understand it is caused by stack overflow.

Is there any clever trick that can make the recursion go deeper?

Like calling another recursive function when it reaches a certain number and clears the stack?

I tried doing this.

#define false 0
#define true 1

int test2(int idx) {
  printf("test2 here\n");
  printf("%d\n",idx);
  test2(idx+1);
  return 0;
}

int test(int idx) {
  if (idx == 262000) {
    return test2(idx);
  }
  printf("%d\n",idx);
  test(idx+1);
  return 0;
}

int main() {
  test(0);
  return 0;
}

But the stack is not cleared. There is still a segfault after printing 262044.

I'm implementing regular expressions to match a file. I read and match the file using a recursive function, but if the file gets too big, there will be a segfault. I will be able to fix that if this question is solved.

test2 still recurses infinitely, so what were you expecting? — WhozCraig, Nov 13 '20 at 07:55
The trick is called [tail calloptimisation](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization). It basically silently compiles certain recursive functions to functions with a loop. If you write your first `test` function to `return test(idx+1);` it would be tail-recursive and thus eligible for such an optimisation. This compiler optimisation isn't done by C compilers AFAIK — ForceBru, Nov 13 '20 at 07:55
I just want the recursion to go deeper. It's ending at 262044 right now. I want it to end at maybe 362044. — qwerty, Nov 13 '20 at 08:00
Instruct your linker to generate an executable file that instructs the OS process loader to allocate a larger stack. One build command and you don't need to change your code at all:) — Martin James, Nov 13 '20 at 08:32
The easiest (and will work 'long term') is to not use recursion. Rather use a loop. — user3629249, Nov 14 '20 at 22:30

score 1 · Answer 1 · answered Nov 13 '20 at 08:03

Is there any clever trick that can make the recursion go deeper?

Recursion is not very clever to begin with and you just found out one of the many reasons why. The obvious "trick" is to increase the stack size, if you have the option to do that on your specific system.

However, recursion should be avoided in most cases. In the few rare cases where it might make sense, it should fulfil two conditions:

There must be a sensible and deterministic way to end the recursive calls.
The recursive call should only be at the end of the function, and only one such call per function. A so called tail call.

Example of tail call:

  int foo (int a)
  {
    ...
    return foo(x);
  }

This kind of recursion can get optimized by the compiler into an inlined loop, so called "tail call optimization". If your compiler can't do that optimization, the function will assault the call stack and kill it.

This means that in the few rare cases where you recursion is motivated (they are very few), you need to disassemble the C code and ensure that no recursive call takes place in the machine code.

score 0 · Answer 2 · answered Nov 13 '20 at 08:27

As mentioned by @Lundin this trick is called using iteration instead of recursion. If you really want to use recursion, you can use something like this:

int max = 100;

int limited_recursion(int dpt, int param)
{
  if (dpt > max)
    return param;

  if (dpt != 0)
    {
      printf("%i\n", param);
      return limited_recursion (dpt + 1, param + 1);
    }

  /* if this is topmost call iterate infititely*/
  while (1)
    param = limited_recursion (dpt + 1, param);
}

int main(void)
{
  limited_recursion(0, 0);
}

However, there is iteration too. Recursion is used for demonstration purposes only and makes this code complicated and less readable. This code can be easily transformed to iterative. In this particular case it's just a while loop infinitely adding 1 to a variable.

Is there any clever trick that can make recursions go deeper?

2 Answers2