In a recursive function, how can I jump to a different function call on the stack?

Question

To make my question more clear, I'll give an example. Say I want to implement a recursive function that sums up the range of numbers from [1-10] and [15-20], skipping (10-15). I would want to add up [15-20] and skip the function calls on stack of (10-15), and continue with [1-10]. How can I do this?

int summation(int x, int y) {
    if(x == y) return x;

    // Catch here and return sum of 15-20 back to calls of 1-10
    if(x == 10) 
        catch(int n) 
            return n;

    int sum = x + summation(x+1,y);

    // Skip function calls 10-15
    if(x==15) throw sum;

    return sum;

}

summation(1,20) // >> 160 or [1-10] = 55, [15,20] = 105

I know how to solve the above example with a different approach, but this example gives an idea of what I'm trying to do.

never use throw and catch for the control flow of your program, get a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — skeller, May 22 '19 at 22:01
@skeller If you have another approach to skipping function calls, I will be happy to accept it. — Amjad, May 22 '19 at 22:02
@Amjad You may use a `std::stack` in a loop instead of recursion, and prune `N` push operations by `pop()`'ing from it's current state. — πάντα ῥεῖ, May 22 '19 at 22:03

score 3 · Accepted Answer · answered May 22 '19 at 22:16

In order to set the try/catch in the right stack frame, you need to know the edge of the skip interval before you recurse deeper. Given that, it will be better to just never make the useless function calls instead of using an exception to unwind them. For example:

int summation(int const x, int const y)
{
    if(x == y) return x;
    int const next = (x==10)? 15: (x+1);  // skip from 10 to 15 directly
    return x + summation(next, y);
}

Avoiding exceptions also gives you the possibility to write the function tail-recursively:

int summation(int const x, int const y, int partial_sum = 0)
{
    partial_sum += x;
    if(x == y) return partial_sum;

    int const next = (x==10)? 15: (x+1);  // skip from 10 to 15 directly
    return summation(next, y, partial_sum);
}

R Sahu · Answer 2 · 2019-05-22T22:28:16.603

2

Keep the function simple.

int summation(int x, int y) {
    if(x == y) return x;
    return x + summation(x+1,y);
}

and use

summation(1, 10) + summation(15, 20);

on the client side.

You can make the client side a little bit simpler by adding another function that takes care of the numbers to skip.

int summation_with_skip(int x1, int x2, int x3, int x4) {
   return summation(x1, x2) + summation(x3, x4);
}

and use

summation_with_skip(1, 10, 15, 20);

If you must have the logic to skip items in the function, you can use

int summation_with_skip(int x1, int x2, int x3, int x4) 
{
   if ( x1 > x4 )
   {
      return 0;
   }

   int s = summation(x1+1, x2, x3, x4)

   if ( (x1 > x2) && (x1 < x3) )
   {
      return s;
   }
   else
   {
      return x1 + s;
   }
}

I like the idea of passing all arguments to the function.

edited May 22 '19 at 22:28

answered May 22 '19 at 22:08

R Sahu

204,454
14
159
270

This is not the problem I'm trying to solve. I only posted that as an Idea. My real problem would be too big and hard to understand if I post it on here. I need to know if there is a way or hack to traversing the stack – Amjad May 22 '19 at 22:12
1

Significantly more efficient to do `summation(1,10) + summation(15,20)` – Ben Voigt May 22 '19 at 22:12
@BenVoigt, agree with you on the efficiency front. If I understand the OP's intent correctly, they have to use `summation(1, 9) + summation(16, 20)`. – R Sahu May 22 '19 at 22:23
1

In the question, the ranges are [1,10] and [15, 20] which are inclusive sets. The "hole" is stated as (10, 15) which is an exclusive set. And the pseudo-code includes 15 in the count (but I guess not 10, although the final comment indicates it should be included). – Ben Voigt May 22 '19 at 22:24

score 1 · Answer 3 · answered May 22 '19 at 22:15

well, this would be a solution without throw&catch

still an odd solution for the given problem

int summation(int x, int y) 
{
    if(x > y) return 0;

    if ((x >= 10) && (x <= 15))
    {
        return summation(x+1, y);
    }
    else
    {
        return x + summation(x+1, y);   
    }
}

In a recursive function, how can I jump to a different function call on the stack?

3 Answers3