Recursive function problem

[zmuro]

Hello. I have a really big problem. I have to write a recursive function in an assembler language, that calculate the n-th term of a sequence in the series:
f( n ) = n^2 * f(n-1) + (n-1)*f(n-2), for n > 2, f(0) = f(1) = f(2) = 1

Can anyone help me with this task? Would any of you know to write this function?

Thanks

[Frank Kotler]

Oh, my f(n) word!

Well, we're not going to do your homework for you, but perhaps we can help if you show us what parts of it you can do. This is a case where it would be really helpful to write the comments first, I think!

You don't say, but I suppose this is supposed to be a "C callable" function? Might as well make it so, anyway. A full stack frame, using ebp as a frame pointer, would probably be wise - might help with debugging. Maybe we'll need some local variables, maybe we can get be with non-volitile registers (ebx, esi, edi) for temporary variables... I think you'll need some...

This is sort of an interesting recursive function, in that it needs to call itself twice. Is that going to present any problems? Offer any simplifications? Is this thing going to "blow the stack" under any conditions? (offhand, I don't think so, but I haven't really thought it through).

You say "for n > 2", but you give a value for f(2), so I assume that means "n >= 2", actually(?). That might be an easy place to start. Can you write a function that returns 1 if the passed parameter is less than or equal to 2?

Then for bigger n, we're going to need to...

; multiply n by itself
; subtract 1 from n and call ourselves
; multiply these two values together
; subtract 2 from n and call ourselves
; multiply this result by n-1
; add that result to the result from the first part
; return that (in eax, presumably)
; whew!

... not necessarily in that order... (I notice that we use n-1 twice...). There needs to be more to it than that - after "call ourselves", "clean up stack", for example, and maybe "save to temporary variable" a time or two...

The arithmetic parts are straightforward enough if you're familiar with the instructions. If not, watch out for the implied operands to "mul" - it'll trash edx behind your back (if you've got your back turned). I ASSume that n is going to be a positive integer?... I suppose you'll need a "test caller" - get n (from the user?) and display the result? You know how to do that part?

I'm short on sleep, and that's about as far as I've thought it through... Why don't you show us how far you can get with it, so we can see where you need help, and I'll sleep on it.

Best,
Frank

[Frank Kotler]

Whoa! I see what you mean by a "really big" problem... Have you got a "crib sheet" on this thing? Is this right for n = 0 to 9?

1
1
1
11
179
4519
163579
8042485
515864093
3194625749

At n = 10, it overflows 32 bits. What input values are we expected to handle? What are we expected to do about overflow? Always understand the specification before you star to code! (he says, belatedly)...

I may be doin' it wrong. This seems to increase almost "too" fast! Maybe I should have slept longer. Maybe another coffee. Maybe some food. I dunno...

Best,
Frank

[zmuro]

I got this far, but I have problems with a second part - (n-1)*f(n-2)
It's not a callable C function. It's a function that is called inside of nasm program.

Code: [Select]

bits 32
extern _printf, _scanf

global _main

section .data

izpis db "%d",0
izpis2 db "%d,%d",0

izpisbr db "%d",0Dh,0Ah,0
N dd 4
dva dd 2


_main:
pushad


;push dword[dva]
push dword[N]


;call funkc
call funkc1

push eax
push izpis
call _printf

add esp,12

popad
ret


funkc1: ;ta izracuna f(n)= n^2*f(n-1); f(1)=f(2)=1

mov eax, [esp+4]
cmp eax, 2
jle .vrniEna


mov ebx, eax
dec ebx
mul eax

push eax ;n^2
push ebx ;n-1
    call funkc1
pop ecx ;n-1
pop ebx ;n^2

mul ebx ;eax = eax*n^2; eax=f(n-1)

push eax ;rezultat prvega dela, zmnozen

push ecx ;dam na sklad n-1
dec ecx
push ecx ;dam n-2
    call funkc1
pop ecx ;f(n-2)
pop ebx ;n-1
mul ebx ;eax =eax*ebx; eax=eax*(n-1)
pop edx ;rezultat prvega
add eax,edx ;sestejem vse skupaj

ret
.vrniEna:
mov eax,1
ret
ret

Edit: Please use CODE Blocks...

[Frank Kotler]

Great! At least we're in agreement - either we're right, or we're both wrong the same way!

At n=9, your version prints a negative number. Changing "%d" to "%u" in the format string gives you one more input value before it overflows. A fairly recent feature... if you put your format string between back-quotes instead of single or double quotes, Nasm will accept "\n" and the like. Handier than ..., 0Dh, 0Ah perhaps.

For comparison, here's how I did it. I do "second part first", but I don't think I gained much from it. Otherwise, it's much the same... (I named the function after you! )

Code: [Select]

;-----------------------------
; f(n) = n^2*f(n-1) + (n-1)*f(n-2)
; f(0)=f(1)=f(2)=1
zmuro:
    push ebp
    mov ebp, esp
    push ebx
    push esi
    push edi

    mov ebx, [ebp + 8] ; ebx = n
    mov eax, 1 ; (preload result)
    cmp ebx, 2
    jbe .done

    lea esi, [ebx - 1] ; esi = n-1
    lea ecx, [ebx - 2] ; ecx = n-2 (temporary!)
    push ecx
    call zmuro
    add esp, 4
    mul esi
    mov edi, eax ; edi = (n-1)*f(n-2)

    push esi ; n-1
    call zmuro
    add esp, 4
    mov ecx, eax ; ecx = f(n-1) (temporary!)
    mov eax, ebx ; eax = n
    mul ebx ; eax = n^2
    mul ecx ; eax = n^2*f(n-1)
    add eax, edi ; add in the (n-1)*f(n-2) from above
   
.done:
    pop edi
    pop esi
    pop ebx
    leave ; mov esp, ebp / pop ebp
    ret
;------------------------

Good job! Add in the call to _scanf and you're done. Don't let 'em enter anything bigger than 9!   (is that okay, or are you supposed to do 64-bit integers? It'll still overflow real soon! "bignum" library?)

Best,
Frank

[zmuro]

Thanks for a fast reply Frank. I must add another condition before function call, so I don't get stack overflow error.