### Author Topic: Recursive function problem  (Read 4918 times)

#### zmuro

• Jr. Member
• Posts: 3
##### Recursive function problem
« on: May 11, 2011, 03:13:13 PM »
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

• NASM Developer
• Hero Member
• Posts: 2377
• Country:
##### Re: Recursive function problem
« Reply #1 on: May 11, 2011, 10:10:20 PM »
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

• NASM Developer
• Hero Member
• Posts: 2377
• Country:
##### Re: Recursive function problem
« Reply #2 on: May 12, 2011, 05:32:12 AM »
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

• Jr. Member
• Posts: 3
##### Re: Recursive function problem
« Reply #3 on: May 12, 2011, 09:25:52 AM »
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 32extern _printf, _scanfglobal _mainsection .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 retfunkc1: ;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 retret`
« Last Edit: May 12, 2011, 09:52:49 AM by Keith Kanios »

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2377
• Country:
##### Re: Recursive function problem
« Reply #4 on: May 12, 2011, 11:48:38 AM »
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)=1zmuro:    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

• Jr. Member
• Posts: 3
##### Re: Recursive function problem
« Reply #5 on: May 12, 2011, 12:48:11 PM »
Thanks for a fast reply Frank. I must add another condition before function call, so I don't get stack overflow error.