Recursive Functions

[stryd_one]

Before I try this and fail and waste my time, has anyone else tried to implement recursive functions? Any luck?

[Lall]

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

[stryd_one]

Thx for the advice mate :)

[Wilba]

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!

[stryd_one]

Thanks man. Last thing I need is the stress of blowing my stack ;)

[audiocommander]

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

[stryd_one]

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  :)