Error: C stack usage 7970184 is too close to the limit

Question

I would like to compute the RSI function, which is given as follows:

RSI = 100 * RS / ( 1 + RS ), where        RS = n_up / n_down

                             and   n_up( t ) = ( 1 - b ) *   n_up( t - 1 )
                                             +       b   *      U( t     ),

                             and n_down( t ) = ( 1 - b ) * n_down( t - 1 )
                                             +       b   *      D( t     ).  

                             where    U( t ) = 1  for P( t ) >  P( t - 1 ) and
                                               0  otherwise;

                             and      D( t ) = 1  for P( t ) <  P( t - 1 ) and
                                               0  otherwise.

So here is my code:

p <- data[,6]


rsi <- function(P,t,n)
{
  U <- function(P,t)
  {
    if (diff(P)[t] > 0) 
    {
      return(1)
    } else {
      return(0)
    }
  }

  D <- function(P,t)
  {
    if (diff(P)[t] < 0) 
    {
      return(1)
    } else {
      return(0)
    }
  }

  recursive.n_up <- function(P,t,b)
  {
    return((1-b)*recursive.n_up(P,t-1,b) + b*U(P,t))
  }

  recursive.n_down <- function(P,t,b)
  {
    return((1-b)*recursive.n_down(P,t-1,b) + b*D(P,t))  
  }

  b <- 2/(n+1)
  rs <- function(P,t,b)
  {
    return(recursive.n_up(P,t,b)/recursive.n_down(P,t,b))
  }
  return(100*rs(P,t,b)/(1+rs(P,t,b)))
}

n <- 14
RSI <- rep(0,length(p)-1)
for (i in 1:length(RSI))
{
  RSI[i] <- rsi(p,i,n)
}

print(RSI)

I get a message error stating:

C stack usage 7970184 is too close to
the limit

So I want to know is my algo design very bad or is this something to expect while using recursive functions? Thank you to help me out to solve this problem.

Solution 1

Yes, your recursion formulation is bad,
both technically and performance-wise:

While a recursion is known that may help to formulate some problems in a smart way, the core logic is, that it has to have some "bottom" line, where the recursion stops from any diving deeper -- being an easily decideable point -- from which the so far nested recursions start to return back and ( being-on-the-road back to the first caller ) the recursion-returning process assembles the correct answer as a side-effect of this emerging back from the deepest level from that known, easily decideable point of a known return value.

Simply put, this is missing in your algorithmisation.

Your code will try to dive deeper and deeper ( back in time ) even at the very first historical bar of the TimeSeries data.

If you handle this case properly, the code will stop its succsidal habit to dive infinitely deep and will start to assemble a result.

Next comes performance:

Recursion is fine for a one-stop calculus.

Recursion is bad idea for repetitive calculus, if the already calculated "steps" get re-calculated again, if a poor value re-use policy enforces to again and again re-dive all the way back again and again to the very same "terminal point", just due to the original ( preformance not-optimised ) recursion formulation.

Let's show it on factorial.

Using its trivial, simplest ever, form of recursion, for illustration purposes, whereas all the principles are relevant to any more complex recursion-based processing - this one just simply fits on a just one SLOC:
factorial( N ) = ( N == 1 ) ? 1 : N * factorial( N - 1 )

If it were for calculating just once a factorial( 15 ), one cannot object a single word against having to go the whole chain of:

fact15 = ( 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 )

where missing any single step would yield the process not to compute the factorial correctly.

The problem would be seen in a different light, if next comes a duty to compute just the next one -- the factorial( 16 )

a performance-ignorant implementation would go the same lane there and back again:

fact16 = ( 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 )

whereas a smart, performance-motivated implementation would never repeat the tail-part of the circus, and would just multiply the head-side:

fact16 = ( 16 * fact15 )

never repeating the part, that has been already computed once.

Do you see the impact?

And imagine the scales of this obvious difference as the recursion-depths gotten grown to some remarkable hundreds, thousands, tens of thousands, hundred of thousands, millions of recursion steps ... repeating each of them any next time again and again and again. No. Never.

This is the core logic of all high-performance, low-latency TimeSeries data-processing, RSI being the clear case, that you have met on your own.

Solution 2

I completely agree with the previous answer provided byuser3666197; you don't have a stop condition in your recursive function. It will go on and on and on ....

In addition, you do something very inefficient in the function. You calculate

return( 100 *       rs( P, t, b )
            / ( 1 + rs( P, t, b )
              )
        )  

So rs(...) is being calculated twice with exactly the same parameters. Why not this:

Z <- rs( P, t, b )
return( 100 * Z / ( 1 + Z )

You will have to integrate a proper stop condition.

Solution 3

For me, I cleared R using the following and got it working:

#Clear plots
if(!is.null(dev.list())) dev.off()

# Clear console
cat("\014") 

# Clean workspace
rm(list=ls())

Comments

[user3666197]

The core inefficiency is not in doing "twice" the recursion inside one time step, but to "repeat all" past recursion steps each next step. That is the core-performance killer in the naive TimeSeries data processing...