2

我认为帖子的标题解决了我的问题。但重申一下，我想知道是否有人有更好的方法来解决这个问题。

/* Write a recursive program to compute lg( N! ) */

#include <iostream>

#include <cmath>

using namespace std;

long double log_base2( long double N ) {
    return log( N )/log( 2.0 );
}

long double lg_n_factorial( long N ) {
    if( 1 == N ) return log_base2( static_cast<long double>( N ) );
    else return lg_n_factorial( N -1 ) + log_base2( static_cast<long double>( N ) );
}

int main( int argc, char *argv[] ) {
    cout << ( lg_n_factorial( 10 ) ) << endl;
    return 0;
}

根据人们的反应，我应该澄清一下，这是书上的问题，书上说要递归地做。我正在练习编程问题，并尝试从其他人那里获得反馈，以便在我努力成为更好的程序员的过程中发现自己的错误。

4

3 回答 3

3

为什么要使用递归？迭代解决方案同样有效：

long double lg_n_factorial( long N ) {
    long double result = 0;
    while (N > 1) {
        result += log_base2(static_cast<long double>(N));
        N--;
    } 
    return result;
}

这样，您可以处理的最大值仅受 的值的约束LONG_MAX，而不是在溢出之前恰好适合您的堆栈的递归调用的数量。

于 2011-08-08T05:13:07.413 回答
2

只是迭代地做？我看不出这个问题需要递归解决的原因。如果您有要求（出于某种原因或其他原因）以递归方式执行此操作，您的方式似乎可以正常工作，尽管您的基本情况可以只是返回 0（任何基数中的 log(1) 为 0）。

此外，无需在每一步都转换为 base 2：您可以在最后执行一次。

于 2011-08-08T05:07:47.867 回答
0

我会说你正确地理解了基本概念。从文体的角度来看，如果你有一个单独的 return 语句，并且 used ，代码会更易读?:，但对于如此短的程序，差异可以忽略不计，不值得担心。更多的是个人品味，我将递归放在最后，以非常清楚地表明它是尾递归。（并且检测尾递归的编译器应该能够重新排序算术并找到它，但是如果递归是最后一件事，人类读者会更清楚地看到它。）

于 2011-08-08T08:30:41.697 回答