MSP430F5529: How to implement recursion in assembly?

1) Re-write the return statement as the completely-equivalent sequence:

int ret;
ret = fib(n-1);
ret += fib(n-2);
return(ret);

2) Recursion per se isn't difficult, just "call fib".

3) It will quickly become important to pass arguments and save (PUSH/POP) local variables in an orderly fashion. (It's very easy to forget this when writing simple assembly programs.) If you've ever heard of an Application Binary Interface (ABI) that's what this is. You can make up your own or adopt one.

4) Based on (3) estimate your required stack size and make sure you have enough (it goes fast).

Actually, I'm trying to make a program that gives n-th Fibonacci number. For example if I give 10, the program should give me "55". I wrote a code but it doesn't work. I know there is something wrong but I couldn't understand how could I fix it. Can you take a look at it please?

Here is the code:

main		mov		#10,R5          ; Program should give 10th Fibonacci number, which is "55".
			clr		R6              ; The result will be stored in R6, so initially it is "0".
			call	#Fibonacci
			nop

Fibonacci:
			cmp		#2,R5           ; Checking if the number is greater than "1".
			jge		fib             ; If yes, then jump to "fib" loop.
			jmp		end             ; If not, then jump to "end".

fib:
			dec		R5              ; Decrease R5 in order to get "n-1"
			mov		R5,R6           ; ret = fib(n-1)
			dec		R5              ; Decrease R5 once more in order to get "n-2"
			add		R5,R6           ; ret += fib(n-2)
			call	#Fibonacci      ; Recursive function

end:		ret

A) I would expect to see two calls to Fibonacci in the Fibonacci() function, followed by some arithmetic. I suggest you name the function "fib" from the C example -- not because the assembler cares, but so you (and we) can see better how the translation works.

B) On the second call to Fibonacci, you overwrite R6 ("ret") from the first call, which wipes out the result. You need to save "ret" over the (recursive) call, which is what I was talking about in (3) above. (I suspect this is the point of your assignment.)

I learned a lot about recursion from reading "The Little Lisper". Sadly out of print but the follow on "The Little Schemer" while not having as cute of a title, does  just as good a job. That might be a better place to start than assembly. Which is all about the details of parameter passing.

There is a lot going on behind the scenes when you make a recursive call in C. The entire state of the local variables are saved on the stack and *then* the function is executed. You must replicate that in your assembly code in order to have any hope of getting it to work, and it will be ugly.

Recursive functions are only elegant in high level languages with a lot of stack space to burn. I have never understood why computer scientists like them so much. 8^)

Hello Bruce.

I was busy doing another assignment, so I didn't think much about this. The deadline for this assignment has passed but I still don't understand how to do this and want to learn it. More precisely, I couldn't figure out how to call the fib() function for the second time. I also used a C-Code to Assembly converter but that didn't help. (The link of the converted code is: https://godbolt.org/z/zK863bxGG) I know it has some redundant lines but this is the best I can achieve.

According to the converted code, the program could not reach the second call. So the lines between 12 and 17 are not used at all by the MSP430.

Can you help me with this?

Thanks.

That link appears to be dead. Have you tried using the MSP430 compiler with "Build Options->Compiler->Advanced->Assembler->Save .lst file"?

You might be overly concerned about the word "recursive". If you pretend the word was never mentioned, how would you write the calls? 

[Edit: Fixed menu chain (I think).]

Can you try this link: https://godbolt.org/z/jbc66EG6b . It should be working now.

I tried MSP430 compiler but it doesn't debug it so I couldn't get the .asm file. I think it's because of the program doesn't store something in registers.

If I write the code without recursive, it should be look like this:

        mov     #10,R4      ; This is the "n" value
        mov     #0,R5
        mov     #1,R6
        
fib:
        tst     R4          ; Check if the "n" is zero
        jz      exit        ; If it's zero, then end the program
        mov     R5,R10      ; Save the R5 value to R10
        add     R6,R5       ; Sum up the previous two numbers and store the result in R5
        mov     R10,R6      ; Change the R6 with R10, which stores the old R5 value
        dec     R4          ; Decrement R4
        jmp     fib         ; Jump back to "fib" loop
        
exit:   mov     R10,R11     ; If the program is over, then show the result in R11

It may contain some errors, I couldn't check it with CCS and MSP430, just thought that it should be like this.

I'm pretty sure an iterative method exists for fib(), but I didn't think that was the point of the assignment. Or was it?