Recursion

[benbaker7]

Hi Folks. I want to come to grips with recursion, but I am unable to find a clear explanation. The best I have been able to come up with, as applied to programming, is "a program that calls itself".
So is the following code an example of recursion?
B1=0
Begin:
For b1=1 to 10
If b1=10 then GOTO flash
B1=b1+1
Pause 1000
Next

Flash:
High c.0
Pause 1000
Low c.0
Pause1000
GOTO flash

I would appreciate your comments please. Ben Baker

 

[bpowell]

Hi Benbaker7,

I don't think your posted code is an example of recursion; that's more what I'd just call "Loops".

Recursion is when a routine calls itself and uses the results of that call in the routine ... the classic programming example is the Fibonacci sequence ... this is a recursive sequence of numbers. Here's an implementation of the Fibonacci routine in C:

int fibonacci(int n) {   
    if(n == 0){      
       return 0;} 
    else if(n == 1) { 
       return 1;   } 
     else {
       return (fibonacci(n-1) + fibonacci(n-2));   }

 }

So, in this example, you can see that (as long as the number passed INTO the function isn't a 0 or 1) the function returns a value that is derived by calling the function again.

Here's a link discussing the Fibonacci Sequence

I'm not sure if this can be done in Picaxe land or not ... since you don't really pass variables to routines, or get results from routines ... I'll noodle on it a bit. I'm sure Hippy will drop 2 lines of code that does the whole trick here in a few minutes, but I'll think on it regardless.

Starting at 0 and going to ten, my quick program yields: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

 

[benbaker7]

Thanks bpowell. Yeah, I figured it' a loop, but I thought it's also recursive. I understand Fibonacci sequence, but not c++.. So if I reformat my previous code to:
B1=0
Begin:
B1=b1+1
If b1=<10 then GOTO begin
If b1>10 then GOTO flash

(followed by the 'flash' routine)

Does this then qualify as recursive given that the base case is 'if b1>10', (the test), and the routine calls itself until b1>10?

 

[bpowell]

Does this then qualify as recursive given that the base case is 'if b1>10', (the test), and the routine calls itself until b1>10?

I guess that meets the criteria!

 

[micrometal]

If I was to be pedantic (which I am) I would say the following was a truer example of recursion ...

loop1:
b = 10
gosub recurse
gosub flash
goto loop1

flash: ' Do something flashy
return

recurse:
b = b - 1
if (b > 0) then gosub(recurse)
return

You can see the difference here in that "recurse" is a subroutine that calls itself, where loop1 (using a goto) is simply a loop, as is the case in the earlier example.

 

[bpowell]

And so begins the first GOTO vs GOSUB war of 2024...

The only differences between the two examples above is: one of them will run successfully on a PICAXE, and the other will not.

Whether calling a routine via GOTO or GOSUB doesn't make that function recursive.

 

[Buzby]

If I was to be pedantic (which I am) I would say the following was a truer example of recursion ...

Your code nearly worked, so I tidied it up.



If you run this in the simulator it's eay to see how it works, especially if you run it slow, or single-step.

Recursion is limited on the Picaxe due to (a) the small gosub/return stack size, and (b) the lack of passing variables to routines.

Some years ago I did try using recursion to solve a maze, but it got too messy, so I gave up !.

 

[benbaker7]

Thanks guys. As 'recursion' from its Latin root seems to mean 'to go back', then as far as a Picaxe program is concerned, and taking into account the replies above, I guess I'll have to content myself with my second example above, which bpowell seemed to think met the criterion for recursion (and it fits into my mindset - at least until a find a more definitive example). Nicklaus Wirth may not agree!

 

[bpowell]

I guess I'll have to content myself with my second example above, which bpowell seemed to think ...

As I tell my wife over and over: I'm always right; just not always at the *right time*.

Your example, Mikrometals, and Buzby's all do about the same thing. I can see the aesthetic desire to use a GOSUB, and have a routine with a return out of it ... but in PICAXE land, it doesn't make too much of a difference ... and in fact, given the limited stack space, the GOTO might be more desirable. Plus, as you can see from Buzby's example: the GOSUB has to "unwind" itself on the way back out, so that takes time that the GOTO didn't.

It's all about finding the right way to do it for our particular use-case. But as far as "recursion" goes, just about everything here meets that definition.

 

[inglewoodpete]

Recursion usually requires local variables in the subroutine. PICAXE can't do that so you have to do things like using free RAM (or scratchpad) and pointers. It's a pretty rare PICAXE project that would need recursion. Rather that writing and debugging recursive code (never simple), I think you'd be better off just stringing a number of subroutine calles and looping and using (one or more) pointer/s.

BTW, the example code in post #1 increments b1 by 2 every loop, so would probably give you some surprises when debugging too.

 

[benbaker7]

Howdy inglewoodpete. Your last paragraph confuses me. I ran it again on the simulator and watched b1 increment by 1 each loop to 11dec, whereby the flash jump occurred. Am I missing a point here? I.e. b1=b1+1.

 

[inglewoodpete]

@benbaker7 Try this version of your code in the simulator, taken directly from post #1, although I have added 1 directive and 2 debugging (logging) commands. It highlights a couple of problems with your original code: stepping by 2s and the 'if' statement is never true.

      #Terminal 9600
      B1=0
Begin:For b1=1 to 10
         If b1=10 then GOTO flash
         B1=b1+1
         Pause 1000
         SerTxd ("B1=",#B1,CR,LF)
      Next
      SerTxd("Dropped through",CR,LF)
      
Flash:
High c.0
Pause 1000
Low c.0
Pause 1000
GOTO flash

 

[benbaker7]

Inglewoodpete - now I see your point. My code was extremely clumsy, and I now see why it increments by 2. I guess I was trying to come to grips with recursion and overlooked the obvious. Tks.