首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >递归函数中的调用堆栈大小:最大调用堆栈大小低于预期

问递归函数中的调用堆栈大小:最大调用堆栈大小低于预期
EN

Stack Overflow用户
提问于 2016-01-02 20:44:54
回答 2查看 2.1K关注 0票数 3

我在我写的递归算法中找到了一个问题。

该算法将在某些输入上抛出一个RangeError: Maximum call stack size exceeded (以Chrome格式)错误。但我追踪到的呼叫堆栈只有大约6k-9k大小。

这个测试 (从这个答案)表示Chrome的最大调用堆栈大小约为42 K。

在运行了一些测试之后,我发现,在递归函数上设置参数似乎降低了可用的调用堆栈大小:

带参数的:在~31k上超过调用堆栈大小(Chrome,边缘上的~15k )

代码语言:javascript
复制
var recursionA = function(a, b) {
    count++;
  if (count < 100000) {
    recursionA(a, b);
  }
}

没有参数的:在~42k上超过调用堆栈大小(Chrome,边缘上为16.5k)

代码语言:javascript
复制
var recursionB = function() {
    count++;
  if (count < 100000) {
    recursionB();
  }
}

看这里的小提琴

  1. 谁能解释,为什么可用的调用堆栈大小显着地低,当函数是用参数调用的。
  2. 因为递归函数需要两个参数:如何利用浏览器的最大调用堆栈大小?
  3. 是否有其他因素可以潜在地减少可用的调用堆栈大小?
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-01-02 20:59:44

  1. 堆栈的大小是一定数量的字节,而不是调用的一些函数。添加到函数调用中的每个参数都会消耗一些内存,因此可用的堆栈更少;
  2. 见上文1
  3. 函数中的变量
票数 2
EN

Stack Overflow用户

发布于 2018-01-11 04:05:14

我只需要做另一个递归函数来调用那个递归函数,并将持续时间分割开来,这样就不会使堆栈达到最大值。这里是一个"callStackOptimizer“的例子,我写它是为了一个复杂而昂贵的fizzbuzz游戏,它是以一种更实用的不变风格编写的,它向您展示了我的意思。

代码语言:javascript
复制
"use strict";

const isDivisibleBy = divisor => number => number % divisor === 0;

const isDivisibleBy3 = isDivisibleBy(3);
const isDivisibleBy5 = isDivisibleBy(5);
const isDivisibleBy3And5 = number => isDivisibleBy5(number) && isDivisibleBy3(number);

const rules = (bool1, bool2, bool3) => (value1, value2, value3) => number => {
    switch (true){
        case bool1(number):
            return value1;
        break;
        case bool2(number):
            return value2;
        break;
        case bool3(number):
            return value3;
        break;
        default:
            return number;
    }
};

const gameConditions = rules(
    isDivisibleBy3And5,
    isDivisibleBy3,
    isDivisibleBy5
);

const fizzBuzzResults = gameConditions(
    "FizzBuzz",
    "Fizz",
    "Buzz"
);

const game = duration => value => (action, array = []) => {
    if (duration > 0){
        const nextValue = action(value);
        return game(duration - 1)(value + 1)(action, array.concat(nextValue))
    }
    else {
        return array
    }
};

const callStackOptimizer = (duration, times = Math.ceil(duration/10000), result = []) => rules =>{
    if (times > 0){
        const value = duration/times;
        const round = game(value)(value * times - value + 1)(rules);
        return callStackOptimizer(duration - value , times - 1, result.concat(round))(rules)
    }
    else {
        return result;
    }
};

const playFizzBuzz = duration => callStackOptimizer(duration)(fizzBuzzResults);

console.log(playFizzBuzz(100000));
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/34570551

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档