RStudio报错：C栈使用接近上限，求调试最小成本递归代码

Hey there! Let's dig into that C stack overflow error you're hitting with your R code for calculating the minimum train travel cost.

First, let's break down why this is happening: your recursive minCostRec function is probably making way too many nested calls, and R's default stack space can't keep up. Recursive approaches without optimization (like memoization) lead to exponential growth in function calls, which quickly eats up the stack.

Let's fix this with two solid solutions—plus a quick workaround if you really want to stick with recursion:

1. Optimize Recursion with Memoization #

Add a memoization matrix to store already calculated results, so we don't waste time (and stack space) recalculating the same (s, d) pairs over and over.

Here's the updated code:

N <- 4
intMax <- 2147483647
data1 <- c(0, 15, 80, 90,
           intMax, 0, 40, 50,
           intMax, intMax, 0, 70,
           intMax, intMax, intMax, 0)
cost <- matrix(data1, nrow = 4, ncol = 4, byrow = TRUE)

# Initialize memoization matrix to store computed results
memo <- matrix(intMax, nrow = N, ncol = N)

minCostMemo <- function(cost, s, d) {
  # Return cached result if we've already calculated this pair
  if (memo[s+1, d+1] != intMax) {
    return(memo[s+1, d+1])
  }
  
  # Base cases
  if (s == d) {
    memo[s+1, d+1] <- 0
    return(0)
  }
  if (s + 1 == d) {
    memo[s+1, d+1] <- cost[s+1, d+1]
    return(cost[s+1, d+1])
  }
  
  min_val <- intMax
  # Check all intermediate nodes
  for (i in (s+1):(d-1)) {
    current_cost <- minCostMemo(cost, s, i) + minCostMemo(cost, i, d)
    if (current_cost < min_val) {
      min_val <- current_cost
    }
  }
  
  # Cache the result before returning
  memo[s+1, d+1] <- min_val
  return(min_val)
}

# Test it out (from station 0 to station 3)
result <- minCostMemo(cost, 0, 3)
print(result) # Should output 65 (0 -> 1 -> 3: 15 + 50)

2. Switch to an Iterative Dynamic Programming Approach #

This completely avoids recursion and stack issues by building up solutions iteratively in a DP table. It's also more efficient for larger datasets.

minCostDP <- function(cost, N) {
  # Initialize DP table: dp[i][j] = min cost from station i to j
  dp <- matrix(intMax, nrow = N, ncol = N)
  
  # Base case: cost to stay at the same station is 0
  for (i in 1:N) {
    dp[i, i] <- 0
  }
  
  # Base case: direct travel between adjacent stations
  for (i in 1:(N-1)) {
    dp[i, i+1] <- cost[i, i+1]
  }
  
  # Calculate costs for paths longer than 2 stations
  for (path_length in 3:N) {
    for (i in 1:(N - path_length + 1)) {
      j <- i + path_length - 1
      dp[i, j] <- intMax
      # Check all intermediate stations k
      for (k in (i+1):(j-1)) {
        current_cost <- dp[i, k] + dp[k, j]
        if (current_cost < dp[i, j]) {
          dp[i, j] <- current_cost
        }
      }
    }
  }
  
  return(dp[1, N]) # Return min cost from first to last station
}

# Test the DP version
result <- minCostDP(cost, N)
print(result) # Outputs 65

3. Temporary Workaround: Increase Stack Limit (Not Recommended) #

If you really need to stick with unoptimized recursion, you can temporarily increase R's stack limit. Note this is system-dependent and risky (it can crash R if pushed too far):

# Check current stack limits
print(getOption("expressions"))
print(.Machine$sizeof.pointer)

# Increase expression limit (adjust as needed)
options(expressions = 100000)

Final Notes #

The iterative DP approach is the most reliable—no stack issues, and it's easier to debug for larger networks. The memoized recursion is a good middle ground if you prefer recursive logic but want to avoid stack overflow.

内容的提问来源于stack exchange，提问作者RikoSK