Why does this recursive function continue even after its base case has been satisfied

Question

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?

I think this is again teh [floating point problem](http://stackoverflow.com/questions/10334688/how-dangerous-is-it-to-compare-floating-point-values) — Bhargav Rao, Sep 01 '15 at 19:18
Don’t compare floating values directly; they can’t be represented well enough to make that reliable. Instead, do something like `abs(a - b) < threshold` to figure out if they are the same (or very similar) — poke, Sep 01 '15 at 19:22

score 7 · Answer 1 · answered Sep 01 '15 at 19:18

The numbers shown to you are not the actual values, because calling str on a number doesn't show you all the digits. If you use repr instead, you'll get this:

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.

Where you can see that the last few iterations aren't the same.

There we go! I thought simply using `str` wasn't going to quite cut it when it comes to floating numbers. Thanks :-) — Juxhin, Sep 01 '15 at 19:19

Martijn Pieters · Accepted Answer · 2015-09-01T19:31:33.790

4

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)

edited Sep 01 '15 at 19:31

answered Sep 01 '15 at 19:14

Martijn Pieters

1,048,767
296
4,058
3,343

3

I think he's referring to the fact that the first few rows have the same value in both columns, not the fact that those are at the beginning rather than the end. – BrenBarn Sep 01 '15 at 19:16
That isn't my concern (actually I did scratch my head at that but after trying some other stuff I noticed this); my concern is why is the same previous and current values are printed multiple times when they shouldn't be. – Juxhin Sep 01 '15 at 19:17
1

they're not really the same number. you're just not printing enough digits to show the "smaller" ones where changes are still occurring. – Marc B Sep 01 '15 at 19:20
I like the extra precision! Thanks Martijn – Juxhin Sep 01 '15 at 19:25
@Juxhin Two different base 2 floating point number might be rounded to look the same even with the extra precision so you really should be careful comparing the decimal representations of binary numbers. – Sylwester Sep 01 '15 at 19:29

score 1 · Answer 3 · answered Sep 01 '15 at 19:32

The problem is that you're comparing real numbers with == operator. It's recommended that you compare real numbers like this:

if abs(cur - prev) <= allowedDifference:

You must define allowedDifference with a very small number like 0.000001 or even smaller.

That's a problem that you have on C/C++ too.

Why does this recursive function continue even after its base case has been satisfied

3 Answers3

Linked