r - 错误 : C stack usage 7970184 is too close to the limit

Question

我想计算 RSI 函数，它给出如下:

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.

这是我的代码:

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)

我收到一条错误消息:

C stack usage 7970184 is too close to
the limit

所以我想知道我的算法设计是否非常糟糕，或者在使用递归函数时是否会出现这种情况？谢谢你帮我解决这个问题。

Answer 1

是的，您的递归公式很糟糕，
无论是技术上还是性能上:

虽然已知递归可能有助于以一种聪明的方式制定一些问题，但核心逻辑是，它必须有一些“底线”，递归从任何更深的潜水中停止——这是一个容易决定的点——到目前为止嵌套递归开始返回并且(正在返回第一个调用者的路上)递归返回过程将正确答案组合为从最深处出现的副作用从已知返回值的已知、容易确定的点开始的水平。

简而言之，您的算法中缺少这一点。

即使在 TimeSeries 数据的第一个历史柱上，您的代码也会尝试越来越深入(及时回溯)。

如果您正确处理这种情况，代码将停止其无限深入的成功习惯，并开始组装结果。

接下来是性能:

递归适用于一站式微积分。

递归对于重复性微积分来说是个坏主意，如果已经计算的“步骤”再次被重新计算，如果一个糟糕的值(value)重用政策强制一次又一次地重新潜入，一次又一次地回到最相同的“终点”，只是由于原始的(性能未优化)递归公式。

让我们用阶乘来展示它。

出于说明目的，使用其简单、最简单的递归形式，而所有原则都与任何更复杂的基于递归的处理相关——这个仅适用于一个 SLOC:
阶乘( N ) = ( N == 1 ) ? 1 : N * 阶乘 ( N - 1 )

如果只计算一次 factorial( 15 )，就不能反对一个词反对必须遍历整个链:

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

缺少任何一个步骤都会导致无法正确计算阶乘。

如果下一个任务是计算下一个 - factorial( 16 )

无视性能的实现会走同一条路来回走:

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

而一个聪明的、以性能为导向的实现永远不会重复马戏团的尾部，而只会增加头部:

fact16 = ( 16 * fact15 )

从不重复已经计算过的部分。

您看到影响了吗？

想象一下随着递归深度增长到惊人的数百、数千、数万、数十万、数百万递归步骤时这种明显差异的规模......下一次一次又一次地重复它们中的每一个然后再次。不，从不。

这是所有高性能、低延迟 TimeSeries 数据处理的核心逻辑，RSI 是您自己遇到的明显情况。