2

总的来说，我想问，

  • 如果一个问题可以通过命令式语言方式和函数式语言方式来解决，那么与命令式语言相比，函数式语言会浪费内存，至少不会节省内存，因为，函数式语言大量依赖递归，递归会推动大量内存堆栈？

  • 然后是上面的问题，从内存优化的角度来看，如果一项工作可以用命令式语言完成，它不应该（至少不会比）使用函数式语言？

上面的问题，其实来自一个算法问题：

在不使用额外空间的情况下保留堆栈：

void insert_at_bottom(node **stack, int data)
{
     if( isempty(*stack) ){
      push(stack,data);
      return;
     }
     int temp=pop(stack);
     insert_at_bottom(stack,data);
     push(stack,temp);
}  


void rev_stack(node **stack)
{
     if( isempty(*stack) ) return;
     int temp = pop(stack);
     rev_stack(stack);
     insert_at_bottom(stack,temp);
}

上面的问题可以通过使用双递归来解决，在我看来，即使它没有在代码中使用额外的内存，它实际上“隐藏”了堆栈中的那些额外空间。

当然，我的问题更笼统，您不必专注于上述特定问题。

感谢您细心的建议！

4

2 回答 2

3

从理论上讲，没有。您始终可以将迭代算法转换为递归算法，反之亦然。假设相同的算法并使用尾调用优化实现，内存消耗的大 O 将完全相同。

在实际意义上，也许。在函数式编程中使用不可变数据结构的风格会占用大量内存。

IMO，使用函数式编程与命令式编程是风格问题。使用最适合代码的那个。而且，如果您需要机器的所有性能，您总是可以编写手动优化的程序集。

于 2014-05-03T22:24:08.720 回答
2

那并没那么简单。

首先，递归，特别是尾递归不需要比循环更多的内存。一般情况下，尾调用也是如此。如果目标机器语言允许，尾调用，无论是否递归，总是可以编译为跳转/分支指令。因此，函数式语言中的程序不需要比命令式语言中的类似程序具有更大的堆栈。

另一方面，为了尽量减少副作用，函数式编程更喜欢处理不可变数据，实际上，纯函数式编程只允许不可变数据。因此，函数式数据结构往往比命令式语言中的可变数据结构更耗费内存。

于 2014-05-04T11:52:40.903 回答