Jump to content
IGNORED

LOGO anyone?


DavidC

Recommended Posts

You can do recursion in BASIC, using GOSUB, but you have to maintain a stack with local data yourself.

Repeating something, FOR - NEXT, isn't recursion. It's iteration.

 

Many recursive algorithms can be implemented in other ways, but frequently not that elegant. Like traversing a tree. That's as simple as can be with a recursive algorithm, but gets pretty complex using other methods.

The penalty for recursion is the overhead of each function call.

Edited by apersson850
  • Thanks 1
Link to comment
Share on other sites

You can do recursion in BASIC, using GOSUB, but you have to maintain a stack with local data yourself.

Repeating something, FOR - NEXT, isn't recursion.

 

Many recursive algorithms can be implemented in other ways, but frequently not that elegant. Like traversing a tree. That's as simple as can be with a recursive algorithm, but gets pretty complex using other methods.

The penalty for recursion is the overhead of each function call.

1 A=A+8

2 GOSUB 1

(RUN, then PRINT A for aprox. free memory)

Does that count as recursion in BASIC?

Edited by jrhodes
  • Like 1
Link to comment
Share on other sites

On 5/23/2020 at 8:27 AM, sparkdrummer said:

@sparkdrummer, man I was able to load and run everything except the stuff on the 99ER.dsk.   What is the trick to getting those to work on classic99?  Something simple, I am sure.   

  • Like 1
Link to comment
Share on other sites

15 hours ago, jrhodes said:

1 A=A+8

2 GOSUB 1

(RUN, then PRINT A for aprox. free memory)

Does that count as recursion in BASIC?

No. Recursion implies a function that calls itself, and, when some condition is true, just returns.

 

More like this (just note that I wrote this very quickly, so I'm not sure if there's any glitch in my thoughts).

ON ERROR GOTO 200
GOSUB 100
PRINT A
STOP
100: A=A+8
IF NOT ENDFLAG THEN GOSUB 100
200: ENDFLAG = -1 :: RETURN

 

  • Thanks 1
Link to comment
Share on other sites

22 hours ago, apersson850 said:

No. Recursion implies a function that calls itself, and, when some condition is true, just returns.

Calls itself, yes, but an exit from recursion is not mandatory, although always makes sense. See the dictionary entry:

 

recursion: see recursion

 

The exit from a recursion is only needed, because resources don't allow endless recursion loops. But a fractal (Mandelbrot) graphics for example could be rendered endlessly. You just limit the recursions programmatically, because a) the display can't show smaller details than a pixel and b) the return stack would grow endlessly but not having endless RAM to store it.

 

Thus

100 A=0
110 GOSUB 200
120 END
200 A=A+1
220 GOSUB 200

would be a legitimate recursion, although

100 A=0
110 GOSUB 200
120 END
200 A=A+1
210 IF A>50 THEN 230
220 GOSUB 200
230 RETURN

makes much more sense and would not, like the first one, result in a stack overflow / out of memory error.

 

Michael

 

Edited by Michael Rittweger
  • Thanks 1
Link to comment
Share on other sites

Yes, you are right in that there are applications where you can get a result from each invocation of the function, like plotting a point or line on a screen. But in the cases when there is no result until the recursion has ended, the whole thing is pointless if there's no condition to exit the recursion. If there isn't, then you'll never get the result.

 

Technically, it's possible to end recursion on a non-predetermined condition. If you are for example using recursion to evaluate moves in games, you can use elapsed time or amount of free memory, or both, as conditions to end the recursion. This means that an application can be written in such a way that it will play a better game if it runs on a faster computer, and/or one with more memory.

Edited by apersson850
  • Thanks 1
Link to comment
Share on other sites

In some dialects of BASIC, doesn't a GOSUB with no corresponding RETURN result in a syntax error? Or is that only "FOR" without "NEXT"?

 

...wait a second; I think I've figured it out:

 

Recursion.thumb.png.93128b702ee02c81e40ac3f90d2beed4.png

 

...Line 1050 could just as easily be a "GOTO", but the whole idea is that the subroutine "calls itself", which is more clear with the use of the "GOSUB". However, if a "GOTO" is used instead, line 1060 is no longer needed because the subroutine returns to the line after 180 where it was called.

 

I just want to send thanks to everyone participating in this thread. I really enjoy thought provoking discussions like this that I find frequently here at AtariAge. Shout-out to @Albert !!!

Edited by almightytodd
Additional thought...
  • Like 2
Link to comment
Share on other sites

From the TML demo program:

RECURSIVESNOWFLAKE.gif.0975fe4af73f4cf12ca5e65ca2161a3f.gif


100 !BINARY SNOWFLAKE FOR TML
110 FOR I=1 TO 3 :: X=1.6 :: L=37 :: A=30 :: B=(L+.01)/X^6 :: GOSUB 130 :: CALL LINK("TURN",120):: NEXT I
120 GOTO 120
130 IF L<B THEN L=L*X :: RETURN
140 CALL LINK("TURN",-A):: CALL LINK("FWD",L):: L=L/X :: GOSUB 130 :: CALL LINK("FWD",-L,A*2):: CALL LINK("FWD",L):: L=L/X :: GOSUB 130
150 CALL LINK("FWD",-L,-A):: L=L*X :: RETURN

 

  • Like 3
Link to comment
Share on other sites

6 minutes ago, senior_falcon said:

From the TML demo program:

RECURSIVESNOWFLAKE.gif.0975fe4af73f4cf12ca5e65ca2161a3f.gif



100 !BINARY SNOWFLAKE FOR TML
110 FOR I=1 TO 3 :: X=1.6 :: L=37 :: A=30 :: B=(L+.01)/X^6 :: GOSUB 130 :: CALL LINK("TURN",120):: NEXT I
120 GOTO 120
130 IF L<B THEN L=L*X :: RETURN
140 CALL LINK("TURN",-A):: CALL LINK("FWD",L):: L=L/X :: GOSUB 130 :: CALL LINK("FWD",-L,A*2):: CALL LINK("FWD",L):: L=L/X :: GOSUB 130
150 CALL LINK("FWD",-L,-A):: L=L*X :: RETURN

That is MONDO COOL!!!

 

 

  • Like 1
Link to comment
Share on other sites

On 5/24/2020 at 10:07 PM, Lee Stewart said:

 

Though you can use GOSUB to effect a kind of recursion, both TI Basic (DEF functions) and XB (DEF functions and SUB subprograms) explicitly proscribe recursive calls. You will get an error message if you try it—DEF, when you define the function, and SUB, when the recursive CALL is actually attempted at runtime.

 

...lee

I was just about to respond to Tursi similarly. I have tried, and failed, to use recursion with XB previously. 

And I disagree that recursion is not a powerful tool in the right hands as it can simplify coding tremendously for certain tasks. It can be difficult to wrap your head around it though. I do use it extensively in my chess program in UCSD Pascal to iterate through all the pieces.

  • Like 1
Link to comment
Share on other sites

Move evaluation in games is frequently best evaluated using recursive techniques.

 

The recursive factorial program is written in an ugly manner. This looks better and is easier to follow.

The main program would be the same. I skipped printing the intermediate steps in the computation.

 

1000 REM Recursive factorial
1010 F=F*R
1020 R=R+1
1030 IF R<I THEN GOSUB 1000
1040 RETURN

In a language which supports proper recursion it gets even more elegant.

function factorial(n: integer): integer;

begin
  if n>1 then
    factorial := n*factorial(n-1)
  else
    factorial := 1;
end;

Calling the procedure would then be like (when using the same variable names as in BASIC)

f := factorial(i);

In most realistic cases, the function should be declared as a real. Considering the word size of our TI, that's most certainly the case.

Edited by apersson850
  • Thanks 1
Link to comment
Share on other sites

16 hours ago, Vorticon said:

I was just about to respond to Tursi similarly. I have tried, and failed, to use recursion with XB previously. 

And I disagree that recursion is not a powerful tool in the right hands as it can simplify coding tremendously for certain tasks. It can be difficult to wrap your head around it though. I do use it extensively in my chess program in UCSD Pascal to iterate through all the pieces.

Hey, I never said it wasn't powerful, I said it wasn't something that made LOGO stand apart from all other languages. ;)

 

Link to comment
Share on other sites

Well, not all other languages. A difference between a language which does support proper recursion, like Pascal, and languages where you can get away with it, like BASIC or assembly, is that in Pascal, the overhead of creating a new activation record on the stack for each call is done automatically. So for each invocation of a recursively called procedure, Pascal doesn't only push the five word activation record (which among other things contain the return address) on the stack, but also space for the function's result as well as all local variables. Which means that if your function is more complex, and requires some local variables inside it to do its math, space for these local variables will be allocated so that each invocation in the recursive call chain has its own set of local variables.

 

That becomes quite messy in BASIC, where you need to prepare an array, and keep track of a (stack) pointer into the array, for each local variable, yourself. For each GOSUB to the recursive procedure you must increase your "stack" pointer into the array, and for each RETURN you have to decrement it.

  • Like 1
  • Thanks 1
Link to comment
Share on other sites

On 5/28/2020 at 6:02 AM, Vorticon said:

I was just about to respond to Tursi similarly. I have tried, and failed, to use recursion with XB previously. 

And I disagree that recursion is not a powerful tool in the right hands as it can simplify coding tremendously for certain tasks. It can be difficult to wrap your head around it though. I do use it extensively in my chess program in UCSD Pascal to iterate through all the pieces.

At one time, I had an Extended BASIC cartridge that did allow recursion (even though I think it was not supposed to).  Years ago, I posted something to that effect on comp.sys.ti - but this program didn’t produce the expected result:

 

100 CALL A

110 SUB A

120 CALL B

130 SUBEND

140 SUB B

150 CALL A

160 SUBEND

 

On my copy of Extended BASIC, this did not result in * RECURSIVE SUBPROGRAM CALL, but rather a never ending * MEMORY FULL IN 120 CALLED IN A CALLED IN B CALLED IN A .... 

 

Thierry has that documented up on his TI 99/4A bug list and states that some Extended BASIC cartridges allowed for recursion and someone in Europe used it and didn’t know it wasn’t allowed in others.  

  • Thanks 1
Link to comment
Share on other sites

I also thought that I had such an Extended Basic version that allowed recursion, but this is obviously not the case, as I have a ROM dump of my Extended Basic, and I cannot reproduce that behavior in MAME. Another theory that I had was that recursion worked without memory expansion (for some obscure reason), but this does not work either. There must be something about it, since other people also believe to have seen that. It can't be just a dream.

  • Like 1
Link to comment
Share on other sites

25 minutes ago, apersson850 said:

It's not that it was the original version? I have version 110, and I've never seen version 100, but I've read about that it does exist.

I am pretty sure the .bin is available.  I *Think* it is on the FinalGrom..but I am not 100% sure about that. 

Link to comment
Share on other sites

The one I had that seemed to have recursion was a black V110 cartridge with the old style label.  I had a beige one at the same time and it did not allow for the recursion (also V110).  Unfortunately I no longer have that special Extended BASIC cartridge. :(

 

Yes, V100 is available for the FinalGROM in the whtech archive.  

 

 

  • Like 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...