Before I try this and fail and waste my time, has anyone else tried to implement recursive functions? Any luck?
Hi Stryd,
My 2cents on the question…
From a pure C coding point of view, there’s no problem in doing recursive functions.
Things to watch out are:
-
that you, of course, need a way to break the circle and go out of your recursion
-
in the embedded world, that you must carefully check that the stack does not overflow with the return address, the parameters and maybe a register or a pointer (as done on the 68HCS08 for example) that would get pushed on the stack.
You can easily get stack overflow so the best is to limit the number of recursions you have. I think a good way to start is to look at the C calling convention to see how it works exactly and to make sure that you do not risk a problem with the stack.
Now all this nice text to end up saying that I’ve never tried that with SDCC on a PIC ;D so I don’t know if that will be of much help…
Best regards,
Lall
Thx for the advice mate 
my 4c on the topic ;D
In the non-embedded world at least, recursive functions in C/C++ are generally avoided because it is all too easy to cause stack overflows depending on the input, i.e. cater for all possibilities.
Take the classic example of a Fibonacci sequence number generator, i.e. calculate the nth number of the Fibonacci sequence, in which each number is the sum of the two previous numbers in the sequence. This is pretty easy to express recursively:
int fib( int n )
{
if ( n <= 2 )
{
return 1;
}
else
{
return fib( n - 1 ) + fib( n -2 );
}
}
[/code]
But then when you call it with n = 1000, your stack blows up.
Of course there's no reason you can't do some things recursively with careful guards and limits on how much you recurse... the quicksort algorithm is a great example of this divide-and-conquer technique and it's harder to blow up the stack because you'd need a really huge number on the input to cause too many recursions.
However, most times when you think a recursive function is appropriate, you can rewrite it as non-recursive using loops and state variables, or just think of another algorithm entirely. For example, the Fibonacci calculation can be done iteratively, like this:
[code]
int fib( int n )
{
int a = 1, b = 1;
for (int i = 3; i \<= n; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
Once you get your head around that, you’ll realise the iterative algorithm is just as complex (i.e. would take just as long to execute) as the recursive one, even if it is a bit harder to understand how it works. The same applies to most other recursive algorithms - there usually is an iterative way of doing the same thing… with no chance of stack overflow!
Thanks man. Last thing I need is the stress of blowing my stack 
hey stryd,
I remembered this topic when I just stumbled upon a self-recursive function I wrote which I’m using for quite some time now without any problems:
/////////////////////////////////////////////////////////////////////////////
// send PANIC! If channel > 15 send panic on all channels (self recursive)
/////////////////////////////////////////////////////////////////////////////
void ACMidi_SendPanic(unsigned char channel) __wparam
{
unsigned char c;
if(channel > 15) {
// send panic on all channels
for(c=0; c<16; c++) {
ACMidi_SendPanic(c);
}
} else {
// send panic
MIOS_MIDI_BeginStream();
MIOS_MIDI_TxBufferPut(MIDI_CC + channel);
MIOS_MIDI_TxBufferPut(MIDI_CC_ALL_NOTES_OFF); // CC 123: ALL NOTES OFF
MIOS_MIDI_TxBufferPut(0x00);
MIOS_MIDI_EndStream();
}
}
as far as I can see (which is not very far in ASM ;D ) the generated ASM code looks nice, too:
;--------------------------------------------------------
; global & static initialisations
;--------------------------------------------------------
; I code from now on!
; ; Starting pCode block
S_ACMidi__ACMidi_SendPanic code
_ACMidi_SendPanic:
; .line 91; ACMidi.c void ACMidi_SendPanic(unsigned char channel) __wparam
MOVFF FSR2L, POSTDEC1
MOVFF FSR1L, FSR2L
MOVFF r0x00, POSTDEC1
MOVFF r0x01, POSTDEC1
MOVWF r0x00
; .line 94; ACMidi.c if(channel > 15) {
MOVLW 0x10
SUBWF r0x00, W
BNC _00125_DS_
; .line 96; ACMidi.c for(c=0; c<16; c++) {
CLRF r0x01
_00127_DS_:
MOVLW 0x10
SUBWF r0x01, W
BC _00131_DS_
; .line 97; ACMidi.c ACMidi_SendPanic(c);
MOVF r0x01, W
CALL _ACMidi_SendPanic
; .line 96; ACMidi.c for(c=0; c<16; c++) {
INCF r0x01, F
BRA _00127_DS_
_00125_DS_:
; .line 101; ACMidi.c MIOS_MIDI_BeginStream();
CALL _MIOS_MIDI_BeginStream
; .line 102; ACMidi.c MIOS_MIDI_TxBufferPut(MIDI_CC + channel);
MOVLW 0xb0
ADDWF r0x00, F
MOVF r0x00, W
CALL _MIOS_MIDI_TxBufferPut
; .line 103; ACMidi.c MIOS_MIDI_TxBufferPut(MIDI_CC_ALL_NOTES_OFF); // CC 123: ALL NOTES OFF
MOVLW 0x7b
CALL _MIOS_MIDI_TxBufferPut
; .line 104; ACMidi.c MIOS_MIDI_TxBufferPut(0x00);
MOVLW 0x00
CALL _MIOS_MIDI_TxBufferPut
; .line 105; ACMidi.c MIOS_MIDI_EndStream();
CALL _MIOS_MIDI_EndStream
_00131_DS_:
MOVFF PREINC1, r0x01
MOVFF PREINC1, r0x00
MOVFF PREINC1, FSR2L
RETURN
So, at least we have a working example here. I know there could be optimisations with Begin- and EndStream(), but… what the heck, it works…
Cheers,
Michael
Thx AC
Problem with mine was that it would push 48 bytes onto the stack every time… I ended up implementing a separate ‘stack’ for the function to avoid stack overflows, but it’s nice to know that they do work