Bug implementing infinite Recursion?
01-04-2018, 04:40 PM (This post was last modified: 01-04-2018 04:45 PM by StephenG1CMZ.)
Post: #1
 StephenG1CMZ Senior Member Posts: 945 Joined: May 2015
Bug implementing infinite Recursion?
I unintentionally implemented an infinite recursion of a function taking a list which should return a real integer (the number of items counter in the list).

The infinite recursion behaved unexpectedly.
The Prime only limits recursion depth in the CAS.

But instead of crashing, the code that should never return an integer, instead returns tthe input list and continues to execute (after several seconds).

Code:
    //Forward  ListCOUNTANYDUPLICATES_SORTED(SORTEDLST);  LOCAL ListANS;//OUTPUT LIST(WHEN NOT RETURNED)   //Also, useful temporary results   EXPORT ListCOUNTANYDUPLICATES (LST)  //Preferred-SORTED  BEGIN   ListANS:=ListSORT(LST);   RETURN ListCOUNTANYDUPLICATES(ListANS);//UNINTENDED RECURSION  END;  EXPORT ListCOUNTANYDUPLICATES_SLOW(LST)  //Caution ऊਉऊ be much slower but may be faster  //REAL LST NO DUPS:5s   //INT LST 8000 DUPS:0.2s  BEGIN   RETURN SIZE(LST)-SIZE(ListREMOVEDUPLICATES(LST));  END;  EXPORT ListCOUNTANYDUPLICATES_SORTED(SortedLST)  //Count how many duplicates in a sortedlist,Return a REAL INT  //({1,9,9}=1 dup, {1,2,2,3,3,3}=3 dup)  //Timings consistent 0.3s  BEGIN   LOCAL II;   LOCAL DUPCOUNT:=0;   IF SIZE(SortedLST)>1 THEN    FOR II FROM 1 TO SIZE(SortedLST)-1 DO     IF SortedLST(II) ==SortedLST(II+1) THEN      DUPCOUNT:=DUPCOUNT+1;     END;//IF    END;//FOR    //ELSE:SMALL LISTS HAVE NO DUPLICATES   END;//IF   RETURN DUPCOUNT;  END;  EXPORT ListExamples()  //In real use, use XXX:=List...()  BEGIN   LOCAL LL:={1,2,3,4,5,6,7,8,9};   PRINT();   PRINT("C");   PRINT("SLOW?");   PRINT(ListCOUNTANYDUPLICATES({0,2,2,2}));//INFINITE RECURSION COMPLETES   //SHOULD RETURN INTEGER (IF RECURSION CORRECTED) BUT RETURNS INPUT LIST   PRINT("D");   PRINT("Exampled");   //RETURN 0;   END;  EXPORT LBUG()  BEGIN   ListExamples();  END;
(A fragment from my List V1.2 code, before bug fix. The intended return procedurename should be ..._SORTED)

Instead of printing C and erroring, the code fragment prints
C
{Input list}
D

At the point where D is printed, the count contains a list instead of an integer, which could lead to subsequent bugs in the user code...It would be better if the recursion were trapped and subsequent code not executed.

Stephen Lewkowicz (G1CMZ)
01-04-2018, 04:43 PM
Post: #2
 Tim Wessman Senior Member Posts: 2,284 Joined: Dec 2013
RE: Bug implementing infinite Recursion?
How would one be able to know if the recursion was intended a) and infinite b)...?

TW

Although I work for HP, the views and opinions I post here are my own.
01-04-2018, 04:49 PM
Post: #3
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
RE: Bug implementing infinite Recursion?
(01-04-2018 04:43 PM)Tim Wessman Wrote:  How would one be able to know if the recursion was intended a) and infinite b)...?

Oh come on, everybody's solved the halting problem these days!

But yeah, if it's returning something rather than dying with a call stack overflow, that's kind of odd.
01-04-2018, 05:06 PM
Post: #4
 Tim Wessman Senior Member Posts: 2,284 Joined: Dec 2013
RE: Bug implementing infinite Recursion?
Not a question of "how to implement" but rather pointing out that just "block the recursion" is not something that is either desirable in many cases or possible within reason as there are many cases when you can have what appears to be an infinite recursion when in actuality it is not.

TW

Although I work for HP, the views and opinions I post here are my own.
01-04-2018, 05:08 PM
Post: #5
 StephenG1CMZ Senior Member Posts: 945 Joined: May 2015
RE: Bug implementing infinite Recursion?
(01-04-2018 04:43 PM)Tim Wessman Wrote:  How would one be able to know if the recursion was intended a) and infinite b)...?

(A) one should note the reference to the code being a code fragment and compare the routine with the corrected code in my List V1.2 program... I didn't mention it just to plug my new program
The corrected code in V1.2 returns a count, and has no recursion.

The code fragment seems to call itself instead and has no obvious terminating condition...
Or am I missing something. Which in my working code would be unintended, though intended here in the interests of intending to show that the recursion is finite and the code continues to execute.
When in the full program, all the calls in ListExamples V1.2 execute after the infinitely finite recursion executes.

(B) The fact that my code prints SLOW and then the input list and then D suggests that on the Android, at least, the recursion is not infinite but is quite deep.

Stephen Lewkowicz (G1CMZ)
01-04-2018, 05:12 PM (This post was last modified: 01-04-2018 05:13 PM by TheKaneB.)
Post: #6
 TheKaneB Member Posts: 175 Joined: Jul 2014
RE: Bug implementing infinite Recursion?
One thing is not clear to me: is the call stack increasing as in a true infinite recursion, or does it stays the same depth as in a infinite iteration caused by recursive calling a function which always hit the base termination condition?

Software Failure: Guru Meditation

--
Antonio
IU2KIY
01-04-2018, 07:05 PM (This post was last modified: 01-04-2018 07:49 PM by StephenG1CMZ.)
Post: #7
 StephenG1CMZ Senior Member Posts: 945 Joined: May 2015
RE: Bug implementing infinite Recursion?
(01-04-2018 05:06 PM)Tim Wessman Wrote:  Not a question of "how to implement" but rather pointing out that just "block the recursion" is not something that is either desirable in many cases or possible within reason as there are many cases when you can have what appears to be an infinite recursion when in actuality it is not.

Of course whether or not it is infinite, or even whether or not it is recursion, is difficult to detect and largely unimportant. The simpler question is: Is there room to add another call to the stack? And if not, should I make it look like the program worked (almost)?

So, if you are struggling to discover some obscure bug such as how your code assigned a list to an integer... Consider the possibility that an infinitely deeply nested procedure call earlier in the execution might have completed and done that for you. In my case, I wasn't tracking down a non-integer count, just wondering why the program was a little slow (but only seconds, not minutes...With some calculations, you might not notice).

Stephen Lewkowicz (G1CMZ)
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)