为什么这个递归函数在它的基本情况被满足之后还继续

Question

我之前在玩/r/dailyprogrammer的简单挑战;在这种情况下，您面临的挑战是发现Dottie Number(~0.739085)。虽然挑战想要它在radians，我决定暂时保持它在度。下面是一些快速代码:

from math import cos
def func(n):
    prev = n
    cur = cos(n)
    if cur == prev:
        print 'Dottie number: ' + str(cur)
    else:
        func(cur)
    print 'Previous = ' + str(prev) + 'tCurrent = ' + str(cur)
func(1)

然而，我注意到输出中的如下示例:

Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133215       Current = 0.739085133215
Previous = 0.739085133216       Current = 0.739085133215
Previous = 0.739085133214       Current = 0.739085133216
Previous = 0.739085133216       Current = 0.739085133214
Previous = 0.739085133213       Current = 0.739085133216
Previous = 0.739085133218       Current = 0.739085133213
Previous = 0.739085133211       Current = 0.739085133218
Previous = 0.739085133221       Current = 0.739085133211
Previous = 0.739085133206       Current = 0.739085133221
Previous = 0.739085133229       Current = 0.739085133206
Previous = 0.739085133195       Current = 0.739085133229
Previous = 0.739085133245       Current = 0.739085133195
Previous = 0.739085133171       Current = 0.739085133245
Previous = 0.739085133281       Current = 0.739085133171
Previous = 0.739085133117       Current = 0.739085133281
Previous = 0.739085133361       Current = 0.739085133117
Previous = 0.739085132999       Current = 0.739085133361
Previous = 0.739085133536       Current = 0.739085132999
Previous = 0.739085132739       Current = 0.739085133536
Previous = 0.739085133922       Current = 0.739085132739
Previous = 0.739085132166       Current = 0.739085133922
Previous = 0.739085134772       Current = 0.739085132166
Previous = 0.739085130904       Current = 0.739085134772
Previous = 0.739085136647       Current = 0.739085130904
Previous = 0.739085128121       Current = 0.739085136647
Previous = 0.739085140777       Current = 0.739085128121
Previous = 0.739085121989       Current = 0.739085140777
Previous = 0.739085149881       Current = 0.739085121989
Previous = 0.739085108474       Current = 0.739085149881
Previous = 0.739085169945       Current = 0.739085108474
Previous = 0.739085078689       Current = 0.739085169945
Previous = 0.739085214161       Current = 0.739085078689
Previous = 0.739085013048       Current = 0.739085214161
Previous = 0.739085311607       Current = 0.739085013048
Previous = 0.739084868387       Current = 0.739085311607
Previous = 0.739085526362       Current = 0.739084868387
Previous = 0.739084549575       Current = 0.739085526362
Previous = 0.739085999648       Current = 0.739084549575
Previous = 0.739083846965       Current = 0.739085999648
Previous = 0.739087042695       Current = 0.739083846965
Previous = 0.739082298522       Current = 0.739087042695
Previous = 0.739089341403       Current = 0.739082298522
Previous = 0.739078885995       Current = 0.739089341403
Previous = 0.739094407379       Current = 0.739078885995
Previous = 0.739071365299       Current = 0.739094407379
Previous = 0.739105571927       Current = 0.739071365299
Previous = 0.739054790747       Current = 0.739105571927
Previous = 0.73913017653        Current = 0.739054790747
Previous = 0.739018262427       Current = 0.73913017653
Previous = 0.739184399771       Current = 0.739018262427
Previous = 0.738937756715       Current = 0.739184399771
Previous = 0.739303892397       Current = 0.738937756715
Previous = 0.738760319874       Current = 0.739303892397
Previous = 0.739567202212       Current = 0.738760319874
Previous = 0.738369204122       Current = 0.739567202212
Previous = 0.740147335568       Current = 0.738369204122
Previous = 0.737506890513       Current = 0.740147335568
Previous = 0.74142508661        Current = 0.737506890513
Previous = 0.735604740436       Current = 0.74142508661
Previous = 0.744237354901       Current = 0.735604740436
Previous = 0.731404042423       Current = 0.744237354901
Previous = 0.750417761764       Current = 0.731404042423
Previous = 0.722102425027       Current = 0.750417761764
Previous = 0.763959682901       Current = 0.722102425027
Previous = 0.701368773623       Current = 0.763959682901
Previous = 0.793480358743       Current = 0.701368773623
Previous = 0.654289790498       Current = 0.793480358743
Previous = 0.857553215846       Current = 0.654289790498
Previous = 0.540302305868       Current = 0.857553215846
Previous = 1    Current = 0.540302305868

输出很好，我按照要求找到了点号，但我不明白为什么递归函数在当前值等于前一个值之后继续执行(因为这是我在函数中定义的基本情况)。这和浮点精度有关吗?值是否在某个点被截断，或者我只是没有正确打印它?

Answer 1

显示给您的数字不是实际值，因为对一个数字调用str不会显示所有的数字。如果你用repr代替，你会得到这个:

Dottie number: 0.7390851332151607
Previous = 0.7390851332151607   Current = 0.7390851332151607
Previous = 0.7390851332151606   Current = 0.7390851332151607
Previous = 0.7390851332151608   Current = 0.7390851332151606
Previous = 0.7390851332151603   Current = 0.7390851332151608
Previous = 0.7390851332151611   Current = 0.7390851332151603
# ... etc.

您可以看到最后几个迭代是不一样的

Answer 2

函数未继续。当递归调用返回时，您可以看到堆栈展开。

换句话说，在您进行递归调用的之后打印的中的Previous = ... Current =信息，因此您看到的是相反的信息。

这些print调用没有显示完整的精度;Python只打印前12位左右的小数，而不是浮点数可以模拟的完整的50多位数字。

您可以显式地将数字格式化为更高的精度:

print 'Dottie number: {:.53f}'.format(cur)

和

print 'Previous = {:.53f}tCurrent = {:.53f}'.format(prev, cur)

请注意，这取决于你的确切平台，无论你是否真的能找到这个数字;在Python 2.7上，在OS X 10.10上，我用完了递归堆栈。您不应该使用精确的匹配，而是使用阈值差异:

from math import cos
def func(n, precision=10):
    prev = n
    cur = cos(n)
    if abs(cur - prev) < (10 ** -precision):
        print 'Dottie number: {1:.{0}f}'.format(precision, cur)
    else:
        func(cur)
    print 'Previous = {1:.{0}f}tCurrent = {2:.{0}f}'.format(precision, prev, cur)

Answer 3

问题是您正在用==运算符比较实数。建议您像这样比较实数:

if abs(cur - prev) <= allowedDifference:

你必须定义一个非常小的数字，如0.000001或更小的allowedDifference

C/c++也有这个问题