情况1 ：
int fun(int num)
{
if (num == 1)
return 1;
else
return num * fun(num - 1);
}
案例二：
int fun(int num)
{
int i = 1;
do
{
i = i * num;
num--;
}
while (num);
return i;
}
我在面试问题中得到了上述问题并询问，哪个更快并且占用更少的内存。我真的不知道，如何找到哪个更快，除了我只是通过数代码行来猜测。但是，我认为，这不是正确的方法。请任何人帮助我，我应该考虑什么来解决这类问题。
更新
我要求的不仅仅是上述情况的一般情况。
这取决于您正在使用的编译器和优化（一个好的编译器可以将第一个代码变成迭代），但是，一般来说，第二个解决方案会更快并且占用更少的内存（因为递归调用需要创建一个堆栈帧）。
关于代码大小，我将第一个实现放入文件f1.c，第二个放入f2.c.
$ gcc -c f1.c f2.c
$ size f1.o f2.o
__TEXT __DATA __OBJC others dec hex
123 0 0 0 123 7b f1.o
119 0 0 0 119 77 f2.o
$ gcc -O3 -c f1.c f2.c
$ size f1.o f2.o
__TEXT __DATA __OBJC others dec hex
372 0 0 0 372 174 f1.o
362 0 0 0 362 16a f2.o
$
请注意，两种实现的代码大小差别很小。有趣的是，优化后的代码比未优化的代码大得多（大约是未优化代码的三倍）。
（编译器：Mac OS X 10.7.5 上的 GCC 4.7.1。）
您应该注意到阶乘（这是这些函数实现的）增长非常快。事实上，13！太大而无法放入 32 位无符号整数 21！太大而无法放入 64 位无符号整数，而 35！太大而无法放入 128 位无符号整数（如果您能找到具有这种类型的计算机）。
另外，请注意假设。我希望迭代解决方案比递归解决方案更快。然而，测量表明并非如此。
测试在配备 2.3 GHz Intel Core i7（和 16 GiB 内存，但内存不是此计算的一个因素）的 MacBook Pro 上运行。
测量表明，当优化代码时，递归解决方案始终比纯迭代解决方案快一点，这与我的预期完全相反，但说明了为什么需要进行性能测量。
# iteration
# Count = 10
# Mean = 0.799869
# Variance = 0.000011
# recursion
# Count = 10
# Mean = 0.750904
# Variance = 0.000014
后来我添加了一个查找表函数，其时间为：
# lookuptab
# Count = 10
# Mean = 0.213836
# Variance = 0.000004
我添加了一个函数，它简单地返回其输入参数来测量测试工具开销，它给出了：
# over-head
# Count = 10
# Mean = 0.211325
# Variance = 0.000001
所以数组查找的计算成本非常小。
如果您曾经怀疑过优化器的能力，那么将优化时间与这些时间进行比较，以获得未优化的构建。
# iteration
# Count = 10
# Mean = 1.852833
# Variance = 0.000020
# recursion
# Count = 10
# Mean = 2.937954
# Variance = 0.000059
和查找表版本：
# lookuptab
# Count = 10
# Mean = 0.730275
# Variance = 0.000026
和开销版本：
# over-head
# Count = 10
# Mean = 0.633132
# Variance = 0.000009
简单地计算代码行数不是一个好的指导方针的原因是不同的行有不同的成本。例如，包含对sin(),cos()和等函数的调用的单行代码tan()（可能）比包含单个整数算术运算和赋值的 20 行代码要昂贵得多。
当比较两个非常相似的函数时（如问题中所示），更复杂的递归往往比简单的迭代慢。但是，正如所证明的那样，当编译器设法优化时，这种猜测的结果可能是错误的，尤其是对于像阶乘这样的简单尾递归函数。
这是一个测试程序：
static int fun1(int num)
{
if (num == 1)
return 1;
else
return num * fun1(num - 1);
}
static int fun2(int num)
{
int i=1;
do{
i = i * num;
num--;
} while (num);
return i;
}
static int fun3(int num)
{
static const int factorial[] =
{ 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600,
};
enum { MAX_FACTORIAL_NUM = (sizeof(factorial)/sizeof(factorial[0])) };
if (num < 0 || num >= MAX_FACTORIAL_NUM)
return 0;
else
return factorial[num];
}
static int fun4(int num)
{
return num;
}
#include "timer.h"
#include <stdio.h>
static void tester(char const *name, int (*function)(int))
{
char buffer[32];
Clock clk;
unsigned long long sumfact = 0;
clk_init(&clk);
clk_start(&clk);
for (int i = 0; i < 100000000; i++)
sumfact += (*function)(i % 12 + 1);
clk_stop(&clk);
printf("%s: %s (%llu)\n", name, clk_elapsed_us(&clk, buffer, sizeof(buffer)), sumfact);
}
int main(void)
{
for (int i = 0; i < 10; i++)
{
tester("recursion", fun1);
tester("iteration", fun2);
tester("lookuptab", fun3);
tester("over-head", fun4);
}
return(0);
}
测试代码小心翼翼地尽可能对称地对待这两个函数，并交替测试每个函数，以减少后台进程干扰性能的机会。（在这些测试中，通常在后台运行的 BOINC 进程被关闭；之前问题的时间经验表明它们严重影响了结果，并在结果中引入了更多的可变性。）
-O3优化 ( ) 构建的原始时间没有查找表或开销函数的早期版本的程序。
recursion: 0.754428 (4357969100681262)
iteration: 0.799330 (4357969100681262)
recursion: 0.749773 (4357969100681262)
iteration: 0.798897 (4357969100681262)
recursion: 0.747794 (4357969100681262)
iteration: 0.800977 (4357969100681262)
recursion: 0.748282 (4357969100681262)
iteration: 0.792708 (4357969100681262)
recursion: 0.748342 (4357969100681262)
iteration: 0.798776 (4357969100681262)
recursion: 0.748377 (4357969100681262)
iteration: 0.801641 (4357969100681262)
recursion: 0.750115 (4357969100681262)
iteration: 0.802468 (4357969100681262)
recursion: 0.750807 (4357969100681262)
iteration: 0.802829 (4357969100681262)
recursion: 0.751296 (4357969100681262)
iteration: 0.796841 (4357969100681262)
recursion: 0.759823 (4357969100681262)
iteration: 0.804221 (4357969100681262)
real 0m15.575s
user 0m15.556s
sys 0m0.027s
没有查找表或开销函数的早期版本的程序。
recursion: 2.951282 (4357969100681262)
iteration: 1.852239 (4357969100681262)
recursion: 2.932758 (4357969100681262)
iteration: 1.851512 (4357969100681262)
recursion: 2.924796 (4357969100681262)
iteration: 1.862686 (4357969100681262)
recursion: 2.946792 (4357969100681262)
iteration: 1.846961 (4357969100681262)
recursion: 2.941705 (4357969100681262)
iteration: 1.849099 (4357969100681262)
recursion: 2.938599 (4357969100681262)
iteration: 1.852089 (4357969100681262)
recursion: 2.930713 (4357969100681262)
iteration: 1.854765 (4357969100681262)
recursion: 2.935669 (4357969100681262)
iteration: 1.851478 (4357969100681262)
recursion: 2.938975 (4357969100681262)
iteration: 1.856979 (4357969100681262)
recursion: 2.938250 (4357969100681262)
iteration: 1.850521 (4357969100681262)
real 0m47.980s
user 0m47.939s
sys 0m0.041s
我注意到两个阶乘函数的代码中都有一个错误；当被要求计算 0! 时，两者都进入长时间运行的循环（并通过溢出 32 位类型调用各种未定义的行为int），它实际上定义良好并且值为 1。这就是为什么在测试工具中调用是(*function)(i % 12 + 1)而不是(*function)(i % 13)我最初写的。
(1) 使用递归，并且可能是堆栈溢出的主题。(2) 是迭代的，并且使用恒定的内存量。我会说 (2) 应该更快。
如果您查看反汇编代码，（1）将具有call比递增/递减循环计数器更昂贵的指令。但是，我相信如果您将 1 作为参数传递给函数， (1) 可能会更快。如果参数大于 1，则 (2) 应该更快地执行。
循环比函数调用更简单，它涉及到它何时被编译为程序集。
您可以通过在调用一段代码之前和之后测量和比较时间戳和内存使用情况来测量所用时间和内存使用情况。
迭代（没有递归的第二个）更快。
通过性能分析检查这篇文章：http: //www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
使用更多内存的原因是在递归解决问题时会占用空间。问题不在于递归本身，因为递归可以实现为不使用堆栈空间（至少在某些语言中，您可以使用“尾”递归而不会受到惩罚）。但是，正如所写，它不是尾递归，递归调用的结果需要与num活动调用的结果相乘（这可以写得更好，抱歉）。