为什么这个递归函数即使在它的基本情况得到满足后仍然继续 [英] Why does this recursive function continue even after its base case has been satisfied

问题描述

我正在玩/r/dailyprogrammer's 简单的挑战更早；在这种情况下，您将面临发现 Dottie 数 (~0.739085) 的挑战.虽然挑战希望它以 radians 为单位，但我决定暂时保留它的度数.下面是一些快速代码:

from math import cos定义函数(n):上一个 = n当前 = cos(n)如果 cur == 上一个:打印 'Dottie 号码:' + str(cur)别的:功能(cur)打印 'Previous = ' + str(prev) + '\tCurrent = ' + str(cur)功能(1)

但是我从输出中注意到以下示例:

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

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

解决方案

该函数没有没有继续.当递归调用 return 时，您会看到堆栈展开.

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

那些打印调用没有显示完整的精度；Python 只打印前 12 位左右的小数，而不是浮点数可以建模的 50 多个数字.

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

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

和

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

请注意，这取决于您的确切平台，您是否会实际找到该号码；在 OS X 10.10 上的 Python 2.7 上，我用完了递归堆栈.您不应该使用完全匹配，而是使用阈值差异:

from math import cosdef func(n, 精度=10):上一个 = n当前 = cos(n)如果 abs(cur - prev) <(10 ** -精度):打印 'Dottie number: {1:.{0}f}'.format(precision, cur)别的:功能(cur)打印 'Previous = {1:.{0}f}\tCurrent = {2:.{0}f}'.format(precision, prev, cur)

I was playing around with /r/dailyprogrammer's easy challenge earlier; in this case you are challenged to discover The Dottie Number (~0.739085). Whilst the challenge wanted it in radians I decided to keep it in degrees for the time being. Below is some quick code:

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)

However I noticed a following sample from the output:

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

The output is fine, I managed to find the dottie number as requested, but I can't understand why the recursive function continued executing even after the current value was equal to the previous one (since that was the base case that I defined in the function). Does this have to do with floating point precision? Is the value being truncated at some point or am I just not printing it correctly?

解决方案

The function did not continue. You are seeing the stack unwind as the recursive calls return.

In other words, the Previous = ... Current = information in printed after you made the recursive call, so you are seeing this information in reverse.

Those print calls do not show the full precision; Python only prints the first 12 or so decimals, not the full 50+ digits a floating point number could model.

You could explicitly format the numbers to a greater precision:

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

and

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

Note that it depends on your exact platform wether or not you'll actually find the number; on Python 2.7 on OS X 10.10 I run out of recursion stack. You should not use an exact match, use a threshold difference instead:

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)

这篇关于为什么这个递归函数即使在它的基本情况得到满足后仍然继续的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！