递归的空间复杂度
是指递归算法在执行过程中所需要的额外空间的量度。在递归算法中，每次递归调用都会创建一个新的函数调用栈帧，用于保存函数的局部变量、参数和返回地址等信息。因此，递归的空间复杂度取决于递归调用的深度。
递归的空间复杂度可以通过递归调用的深度来衡量。每次递归调用都会将当前函数的局部变量和参数保存在栈帧中，当递归调用结束后，对应的栈帧会被销毁。因此，递归的空间复杂度通常是O(n)，其中n表示递归调用的深度。
递归的空间复杂度也可以通过递归函数中所使用的额外空间来衡量。额外空间指的是除了函数调用栈帧之外的空间，例如全局变量、静态变量等。如果递归函数中没有使用额外空间，那么递归的空间复杂度可以认为是O(1)。但是如果递归函数中使用了额外空间，那么递归的空间复杂度就会增加。
递归的空间复杂度在实际应用中需要注意，特别是在处理大规模数据或者递归调用深度较大的情况下。如果递归的空间复杂度过高，可能会导致内存溢出或者性能下降。
腾讯云相关产品和产品介绍链接地址：
- 腾讯云函数（云原生）：https://cloud.tencent.com/product/scf
- 腾讯云数据库（数据库）：https://cloud.tencent.com/product/cdb
- 腾讯云服务器（服务器运维）：https://cloud.tencent.com/product/cvm
- 腾讯云CDN（网络通信）：https://cloud.tencent.com/product/cdn
- 腾讯云安全产品（网络安全）：https://cloud.tencent.com/solution/security
- 腾讯云音视频处理（音视频、多媒体处理）：https://cloud.tencent.com/product/mps
- 腾讯云人工智能（人工智能）：https://cloud.tencent.com/product/ai
- 腾讯云物联网（物联网）：https://cloud.tencent.com/product/iotexplorer
- 腾讯云移动开发（移动开发）：https://cloud.tencent.com/product/mobdev
- 腾讯云对象存储（存储）：https://cloud.tencent.com/product/cos
- 腾讯云区块链（区块链）：https://cloud.tencent.com/product/baas
- 腾讯云虚拟地球（元宇宙）：https://cloud.tencent.com/product/ve
相关·内容
1回答
BFS:递归与迭代
、、、、
用递归和迭代的方式编写BFS树遍历算法有什么好处吗？在我看来，迭代是可行的，因为它可以在一个简单的循环中实现：
队列根节点
去队列节点和检查
让它的孩子排队
进入第二步
递归有什么好处吗？它似乎更复杂，没有任何优势。
提前谢谢..。
浏览 1提问于2018-03-07得票数 4
2回答
我想知道空间复杂度最低的递归程序和非递归程序的空间复杂度之间的区别，我知道递归在其操作中使用堆栈，但递归总是增加空间complexity.Can递归有助于降低空间复杂度吗?我也将感谢对recursion.Please中堆栈使用的良好教程的任何指导，如果可能的话，也提供了一个简短的说明示例。
浏览 5提问于2013-09-02得票数 1
回答已采纳
1回答
我对haskell最大的问题之一是能够(正确地)预测haskell代码的性能。虽然我有一些更难的问题，但我意识到我几乎没有理解。
举个简单的例子：
count [] = 0
count (x:xs) = 1 + count xs
据我所知，这并不是严格意义上的尾部调用(它应该在堆栈上保留1)，所以看看这个定义--我能从中推断出什么呢？count函数显然应该有O(1)的空间需求，但是这个函数有吗？我能保证它会或不会吗？
浏览 0提问于2011-09-05得票数 1
回答已采纳
4回答
设F(n)=0.5F(n-1)，F(0)=1
写一个函数fun1，一个计算n项的递归函数
b.编写一个函数fun2，一个非递归函数来计算n项
c. fun1的时间复杂度是什么?从哪个n项出发，在空间复杂性方面使用fun1和fun2更好
一般来说，函数计算序列{1,1/2,1/4,1/8，.}的n项。
一个。
double fun1( int n ){
if (n == 0)
return 1;
else
return 0.5*fun1(n-1);
}
b.
double fun2( int n ){
double sum = 1
浏览 2提问于2019-02-03得票数 4
3回答
int f(int n)
{
if (n <= 1)
{
return 1;
}
return f(n - 1) + f(n - 1);
}
我知道时间复杂性是O(2^n)，我理解原因。
但我不明白为什么空间复杂性是O(n)。有人告诉我，这是因为在任何时候都只有n节点，但这对我来说没有意义。
浏览 7提问于2016-12-31得票数 10
回答已采纳
1回答
我试图确定我创建的这个算法的时间和空间复杂性，以查找Python中数组的所有排列。时间复杂度O(sum_{k=1}^N P(n，k))，其中P(n，k)是k因子的置换吗？
class Solution:
def permute(self, vals):
answer = [vals]
def backtrack(i, curr_arr):
if i >= len(vals):
return
curr_val = curr_arr[i]
for j
浏览 14提问于2021-12-18得票数 0
我使用分而治之的方法实现了一个合并排序算法，其中一个数组被分成两个子数组。
在我的代码中，我重复使用插入排序算法对合并排序中的子数组进行排序。这种方法是正确的还是我必须使用不同的排序方法来对合并排序中的子数组进行排序？
对于合并排序算法的理解，一切都很清楚，但是在实现合并排序时，如何在不使用递归策略的情况下将数组划分为n个子数组。
递归还是非递归是实现合并排序的有效方法？
下面是我在github中的代码片段：
从实现的角度来看，我了解到我的代码是错误的，因为我只将数组划分为两个子数组，而不是n子数组。
从算法实现角度清楚地理解合并排序所需的任何帮助。
以下是代码：
package com.al
浏览 1提问于2020-05-02得票数 1
回答已采纳
2回答
我编写了递归和迭代二进制搜索的算法：
递推
AlgorithmBinSrch(a, i,l,x)
// Given an array a[i :l] of elementsin nondecreasing
// order,1<i <=l,determinewhetherx is present,and
// if so,return j suchthat x = a[j];elsereturn 0.
{
if (l =i) // If Small(P) {
if(x=a[i])
return i;
else
浏览 0提问于2019-08-13得票数 12
回答已采纳
3回答
在以下两个案例中，我对时间和空间复杂性有疑问。
区块报价
案例I:
递推:阶乘计算。
int fact(int n)
{
if(n==0)
return 1;
else
return (n*fact(n-1));
}
这里为什么时间复杂度变成2*n，空间复杂度与n成正比。
和
Case II:
迭代：-
int fact(int n)
{
int i, result = 1;
if(n==0)
result = 1;
else
{
for(1=1;i<=n;i++)
浏览 5提问于2012-05-21得票数 0
回答已采纳
4回答
这只是一个计算空间复杂度的测试函数，如果我们考虑堆栈帧的数量，而不是o(n)，那么for循环中的a和b数组和2d数组(在每次递归调用中也会占用一些内存)呢?我的教授告诉我们，空间复杂度是堆栈帧的大小，但它也占用了循环的一些空间。我是否应该同时考虑堆栈帧和两个数组和2d数组，或者给予它们任何一个优先级？
我只是专注于空间复杂性，所以忘记结果或垃圾收集吧。
testfun(n){
if(n==0)
return;
int c[10][10];
int *a=malloc(sizeof(int)*n);
int *b=malloc(sizeof(int)*n);
fo
浏览 1提问于2018-10-20得票数 2
回答已采纳
1回答
我正在阅读“破解编码访问”一书，并遇到了一个问题：“编写一个程序，按升序排列堆栈。您可以使用额外的堆栈来保存项，但不能将元素复制到任何其他数据结构中(例如数组)。堆栈支持以下操作: push、pop、peek、isEmpty。”
这本书用O(n^2)时间复杂度和O(n)空间给出了一个答案。
然而，我发现使用快速排序方法在O(n log n)时间复杂度中提供了一个答案。
我想知道的是空间复杂性O(n^2)？因为对该方法的每次调用都涉及初始化另外两个堆栈，以及另外两个递归调用。
我对太空的复杂性还有点动摇。我不确定这是否是O(n^2)空间，每个递归调用产生的新堆栈都小于一个级别上的堆栈。
如果有人
浏览 1提问于2014-02-24得票数 0
回答已采纳
1回答
尽管我之前在stackoverflow上读了一些问题，看了一些视频，包括this one，但时间和空间的复杂性让我摸不着头脑。我需要找到这个算法的时间和空间复杂度。 public static int aPowB(int a, int b){
if(b == 0){
return 1;
}
int halfResult = aPowB(a, b/2);
if(b%2 == 0){
return halfResult * halfResult;
}
r
浏览 12提问于2020-11-01得票数 1
3回答
时间和空间复杂度是什么：
int superFactorial4(int n, int m)
{
if(n <= 1)
{
if(m <= 1)
return 1;
else
n = m -= 1;
}
return n*superFactorial4(n-1, m);
}
它递归地运行，将n的值减1，直到它等于1，然后它将把m的值减1，或者在m等于1的情况下返回1。
我认为复杂度取决于n和m，所以可能是O(n*m)。
浏览 0提问于2009-02-10得票数 0
所以我知道递归在顺序遍历中的空间复杂度是O(h)，而不是O(n)，因为h=树的高度，n=树中的节点数。
为什么会这样呢？假设这是遍历的代码：
public void inorderPrint (TreeNode root) {
if (root == null) {
return;
}
inorderPrint(root.left);
System.out.println(root.data);
inorderPrint(root.right);
}
我们将n个内存地址推送到调用堆栈，因此，空间复杂度应该是O(n)。
我遗漏了什么？
浏览 0提问于2016-12-18得票数 18
回答已采纳
1回答
我正在尝试学习自排序，并发现资源是稀缺的。
我的问题是，在切换到堆排序之前，深度是如何计算的？有floor(log(length_of_data))x2，但我见过使用其他东西。原因是什么？我说的对吗?算法希望坚持使用快速排序，直到由于内存原因而需要切换到堆排序？
浏览 1提问于2016-10-11得票数 0
3回答
我正在实现一个程序来对可能无法放入内存的大文件进行排序。所有的文件都是按行排序的，所以我想用一个列表来做。
我已经计算了内存中有多少行可以将文件拆分成较小的文件，但我不知道内存中需要多少空间才能对N个元素的列表进行排序。
问题是，知道元素的最大数量(已知大小的字符串)和可用内存，List.Sort方法将需要多少内存空间？
浏览 2提问于2012-07-13得票数 0
回答已采纳
def square(n):
def same_number(n):
if n == 0 :
return 0
else :
return 1 + same_numer(n - 1)
return n * same_number(n)
据我所知，same_number的时间复杂度和空间复杂度都是O(n)。然而，被称为same_number的square的时间和空间复杂度是什么呢？它只有1，还是你必须考虑到same_number？
浏览 0提问于2018-02-03得票数 0
有人能举例说明我们如何计算这两种遍历方法的时间和空间复杂度吗？
另外，深度优先遍历的递归解决方案如何影响时间和空间复杂度？
浏览 1提问于2012-03-24得票数 76
回答已采纳
2回答
我知道堆排序的空间复杂度是O(1)。但是对于一个递归程序，在计算空间复杂度时，它的深度--也就是它进行的递归调用的次数--也是计数的。因此，相同代码的迭代和递归方法的空间复杂度不同。那么，递归处理堆排序的空间复杂度是多少呢？
浏览 2提问于2019-01-12得票数 0
回答已采纳
1回答
我有这两种方法来求给定数'n‘的Fibonacci级数。一个用回忆录。
我想知道这两种方法的空间复杂性有何不同：
public static int fib(int n, int[] mem){
if(n ==0 || n ==1 ){
return n;
}
if(mem[n] > 0 ) {
return mem[n]);
}
mem[n] = fib(n-1,mem) + fib(n-2,mem);
return mem[n];
}
没有回忆录：
public static
浏览 0提问于2018-05-15得票数 2
回答已采纳
3回答
这让我有点困惑。当约束如下时，我应该如何解决给定的问题：
1)不使用额外的空间:例如:如果我想对一个给定的数组进行排序，我有几种方法。冒泡排序，它保持交换(只有循环，没有递归)。我相信这不会占用额外的空间。如果我使用递归来对元素进行排序，会发生什么情况？它是否等同于“不使用额外空间”，或者使用的堆栈被计入算法的空间复杂度？
2) O(1)空间: O(1)空间的含义是什么？这是不是意味着恒定空间。现在，如果它是常量空格，那么请评论以下情况：
a)如果我在冒泡中进行交换，则借助第三个变量进行排序。它不是一个额外的空格吗，它不会依赖于输入的大小，所以它是在恒定的空格中。
b)此外，如果我使用计数排序
浏览 0提问于2012-06-01得票数 9
回答已采纳
4回答
我在这里用了一个简单的例子。
function factorial(n)
if n==1 return 1
else return n*factorial(n-1)
function factorial(n)
result = 1
for i = 1 to n
result *= n
return result
或者是递归的、具有记忆化的函数，而不是动态编程，后者需要迭代数组并填充值，等等。
我知道有时候递归是不好的，因为你可能会耗尽内存(尾递归？)堆(或栈？)，但这会影响O表示法吗？
递归记忆算法是否具有与迭代版本相同的O符号/速度？
浏览 2提问于2014-01-15得票数 4
1回答
我正在阅读Sean的"stb.h“库的源代码，我有一个关于快速排序的实现的问题。
因此，我对以下节选感到特别困惑：
/* recurse on smaller side, iterate on larger */ \
if (j < (n-i)) { \
STB_(FUNCNAME,_quicksort)(p,j); \
p
浏览 0提问于2018-12-12得票数 1
回答已采纳
位置和空间复杂度O(1)是否意味着不同的东西？如果是的话，谁能解释一下区别吗？
浏览 2提问于2015-10-23得票数 4
1回答
求二叉树最大深度时的最坏情况
、、、、
这是查找二叉树最大深度的伪代码：
maxDepth(Node N)
1. If Nodes is leaf node then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( N->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( N->right-sub
浏览 2提问于2017-09-20得票数 2
回答已采纳
2回答
我理解了基本原理，如果我有一个这样的函数：
int sum(int x, int y, int z) {
int r = x + y + z;
return r;
}
它需要3个参数单位的空间和1个局部变量的空间，并且这永远不会改变，所以这是O(1)。
但是如果我有一个像这样的函数：
void add(int a[], int b[], int c[], int n) {
for (int i = 0; i < n; ++i) {
c[i] = a[i] + b[0]
}
}
这需要N个单位用于a，M个单位用于b，L个单位用于c，1个单位用于i和n
浏览 1提问于2015-05-14得票数 17
1回答
不知何故，我设法编写了一个算法，用于从二叉树的无序和前置遍历数据中构建二叉树。
我不确定如何计算该算法的时间和空间复杂度。
我猜是
first pass --> n(findInNode) + n/2 (constructTree) + n/2 (constructTree)
second pass --> n/2(findInNode) + n/4 (constructTree) + n/4 (constructTree)
etc..
所以应该是(3 3logn)
如果我错了，请纠正我。
public class ConstructTree {
public stati
浏览 2提问于2012-07-02得票数 1
我知道空间复杂度从O(n)下降到O(log )。但是时间复杂度又如何呢？执行Quick Sort的时间是否与常规版本相同？
浏览 0提问于2011-11-06得票数 0
The problem：在MxN网格中，从左上角到右下角寻找许多可能的方法，而您只能向下或向右移动。
这是我写的两种算法。结果看起来很好，但我无法计算出时间和空间的复杂性，我对复杂程度有一些猜测，但我无法以“正确”的方式来证明它们。
朴素算法：
function gridTravel(m, n) {
if(m<1 || n<1) return 0;
if (m === 1 || n === 1) return 1;
return gridTravel(m-1, n) + gridTravel(m, n-1);
};
co
浏览 2提问于2021-09-16得票数 1
回答已采纳
我得到了一个字符列表，并告诉我写出这些字符的所有'combinations' (不完全是组合)。 e.g. [w,x,y,z] -> w,wx,wxy,wxyz,wy,wyz,wz| x,xy,xyz,xz| y,yz 这个的space and time complexity是什么？ 对于TC，我在想，当我们迭代列表时，对于每个元素，我们有越来越少的组合可供选择-但这不是完全的组合；你知道这个模式是什么吗？ 与SC类似，如果我可以确定每个元素的模式，那么TC和SC将很容易确定。
浏览 16提问于2021-08-22得票数 0
回答已采纳
2回答
第一职能：-
void strange (int n,int k)
{
int i;
if(k > n)
return;
for(i=k; i<n; i++)
printf("?");
strange(n, k+2);
return;
}
第二职能：-
void weird(int n, int k)
{
int i;
if(n <= 0 || (k <= 0))
return;
k *=2;
for(i=0; i < k; i++){
printf("?");
weird(n/2, -n
浏览 4提问于2015-06-07得票数 1
回答已采纳
我知道在递归算法和迭代算法之间确实存在空间复杂度的差异。但是，它们之间的时间复杂度是否也存在差异？例如:如果我有一个递归地计算列表中节点数量的程序，然后我实现了与迭代相同的程序，那么我在时间复杂度上是否会有任何差异，即O(n)？谢谢
浏览 0提问于2011-11-01得票数 0
回答已采纳
下面是一段python代码，它使用Goodrich and Tamassia这本书中的二进制递归来查找元素列表的总和。
def binary_sum(S, start, stop):
"""Return the sum of the numbers in implicit slice S[start:stop]."""
if start >= stop: # zero elements in slice
return 0
elif
浏览 0提问于2019-03-28得票数 0
2回答
假设我有一个递归函数，它工作在一个具有n节点和高度log(n)的完全平衡的二叉树上，并调用树根下面的函数。
void printPaths(TreeNode root, int[] array, int depth){
if (root == null){
print array;
}
array[depth] = root.data;
printPaths(root.left, array, depth + 1);
printPaths(root.right, array, depth + 1);
}
array = new int[
浏览 5提问于2013-07-24得票数 1
回答已采纳
3回答
阶乘的递归计算应该很慢，因为问题的复杂性很高。为什么我的基本实现不是很慢呢？我很好奇，因为这应该是一个糟糕的方法的教科书例子。
是因为C#程序中的一些内部优化或缓存导致的吗？
using System;
using System.Diagnostics;
using System.Numerics;
namespace FactorialRecursion
{
class Program
{
static void Main(string[] args)
{
Stopwatch stopwatch = new Stopw
浏览 5提问于2016-09-24得票数 3
2回答
我感兴趣的是如何计算递归函数的时间和空间复杂度，如置换、斐波那契(描述为)
一般来说，我们可以在许多地方进行递归，而不仅仅是在置换或递归上，所以我正在寻找一种通常遵循的方法来计算空间复杂度。
谢谢
浏览 0提问于2010-12-02得票数 4
回答已采纳
1回答
考虑到A是k数组的数组。每个内部数组都进行排序，并包含m个元素。
给出了合并A中K排序数组的算法：
// A is array of sorted arrays
K-arrays-merge(A)
1. if A.length == 1
2. return first element of A
3. half = length[A] / 2
4. firstHalfArray = new array[half][m];
5. secondHalfArray = new array[half][m];
6. for (i = 0; i < half; i++)
浏览 0提问于2018-03-15得票数 1
回答已采纳
1回答
这是我学校一篇过去的期中论文中的一个问题.下面是一个图表，显示机器人将如何移动，从同一张纸。我的担忧在橙色部分表达了。
基本上，当机器人在左边遇到一个未被访问的网格广场时，它会向前移动，然后向左转。
机器人横越3码网格的指令顺序是：(“F”、“T”、“F”、“T”、“F”、“F”、“F”)，其中“F”表示向前移动一平方，而“T”表示向左转90度。注意，最后一条指令导致机器人退出网格。函数gen_seq以网格的大小作为输入，并返回一系列指令给机器人横越网格。指令序列是一个元组，包含字符串'F‘和'T’，它们表示前向命令和转折命令。
提供函数gen_seq的递归或迭代实现
浏览 0提问于2018-03-26得票数 8
1回答
递归的空间复杂度
、、
对于一个简单的程序：
public class solution{
public void start(int m, int n){
for(int i = 0; i < m; i++)
recur(n);
}
public void recur(int n){
for(int j = 0; j < n; j++)
recur(n-1);
}
}
有人能帮我分析一下空间复杂度吗？我认为它是O(m*n)。
谢谢。
浏览 6提问于2016-07-29得票数 2
回答已采纳
1回答
我试图制作一个程序，通过将数组分成两部分来递归地搜索元素，您能知道下面代码的时间复杂度吗？
public boolean search(List<Integer> A, int B,int l,int r) {
if(l==r) {
if(A.get(l)==B) {
System.out.println("Found at index : "+l);
return true;
}else {
return
浏览 2提问于2022-07-31得票数 -1
1回答
def maxN(n:list[int])-> int:
if len(n)==2:
if n[0] > n[1]:
return n[0]
else:
return n[1]
if len(n) ==1:
return n[0]
else:
mid = len(n)//2
first = maxN(n[0:mid])
second= maxN(n[mid:])
if first>second:
浏览 0提问于2022-08-04得票数 0
回答已采纳
当空间是问题时，我很难确定递归函数何时比它们的迭代对应函数次之。在编写递归函数时，如果不是尾递归的话，空间复杂度是否至少与递归调用的深度一样大？
例如，让我们使用递归从链接列表中删除重复项。这可以通过在O(n^2)时间和O(1)空间中的迭代方法来实现。但是递归变量也是O(1)空间吗？
removeDuplicatesRecursive() {
let current = this.head;
while (current.next) {
if (this.head.data === current.next.data) {
current.next
浏览 0提问于2018-07-28得票数 3
回答已采纳
3回答
考虑以下C-函数：
double foo (int n) {
int i;
double sum;
if (n == 0) return 1.0;
else {
sum = 0.0;
for (i = 0; i < n; i++)
sum + = foo (i);
return sum;
}
}
上述函数的空间复杂性是
1) O(1)
2) O(n)
3) O(n!)
4) O(n^n)
在以上问题中，我认为答案应该是(2)，但答案是(3)选项。虽然它是递归函数，但是堆栈的
浏览 2提问于2014-01-13得票数 3
回答已采纳
如果递归解决方案在返回一个级别之前连续调用自己大约N次，则空间效率充其量是O(N)，因为N次调用中的每一次都会占用一定数量的堆栈空间。
这是否也意味着时间效率充其量也是O(N)，因为递归函数内部的代码类似于运行~N次的内部循环代码？
浏览 0提问于2012-07-08得票数 0
回答已采纳
2回答
我理解下面快照中的代码是如何工作的，但我很好奇，我如何知道它的时间和空间复杂性？
我知道这取决于“b”变成零所需的时间。有什么数学方法可以让我找到这个吗？我知道这不会发生在数百万次的递归中。但还是很好奇会发生多少次递归？
问题:在不使用任何算术运算的情况下添加两个数字-
浏览 3提问于2016-02-05得票数 2
回答已采纳
3回答
我想展示快速排序空间复杂性的最坏情况。
我在想，快速排序不使用辅助数组，它只在分区子例程上创建了一些辅助变量，但它只操作数组中的项。所以，很明显，我的结论是它使用了O(n)空间。
但是在互联网上搜索，我发现在最坏的情况下，快速排序的空间复杂度是O(log )。
我只是不明白为什么在最坏的情况下它比输入数组占用更少的空间？
附言:我正在读“算法导论”这本书。
我已经尝试过对算法上的所有变量声明进行计数。
QUICKSORT(A, p, r)
if p < r
q = partition(A, p, r)
QUICKSORT(A, p, q - 1)
浏览 1提问于2019-09-10得票数 1
我想知道是否有人可以向我解释这两个算法的空间复杂性是如何工作的。我已经读过了，但如果我理解正确的话，它们似乎是矛盾的。
例如，我对链表将如何影响空间复杂性感兴趣，这个问题说它使其更快？；
然而，这个问题说这无关紧要；
现在我对编程有点新手，我想更好地理解这个理论，这样哑巴语言就会很受欢迎。
浏览 4提问于2018-03-17得票数 1
2回答
我是在一次面试中被问到的，这是一种有效的解决问题的方法。
现在我可以做两件事：
从i=0开始到i= n/2，比较ith和n-ith字符是相等的。
我可以使用递归来检查第一次和最后一次是否相同，而字符串的其余部分是一个淡色码。
第二种是递归的。我的问题是，算法的递归版本和非递归版本的空间复杂度有什么不同？
浏览 4提问于2012-05-30得票数 10
回答已采纳
4回答
我在考虑递归函数。使用一个简单的函数，例如递归打印链接列表的函数：
void print(list *list){
if(list){
cout << list->data
print(list->next);
}
}
起初，这似乎是一个相当无害的函数，但它不是在每个堆栈帧中存储一个地址(由变量列表标记)吗？假设没有尾部优化。我们需要N个地址的空间，其中N是列表的大小。所需空间与列表的大小成正比增长。
如果不将至少一个局部变量或参数存储在堆栈上，我就无法想象如何实现递归函数。因此，似乎每个递归函数最多都具有线性空间复杂度。如果是这样的话，那么
浏览 5提问于2013-11-17得票数 6
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
云直播活动推荐
腾讯云开发者
