Recursion in NASM: Fibonacci

I am having a hard time getting recursion to work. Well, recursion for a n! factorial calculator wasn't that hard, took me about half a day to figure it out.

   mov eax, [input]

   call factorialator



   jmp quit

 ;   

factorialator:

   cmp eax, 0

   je return

   push eax

   dec eax

   call factorialator

  ;

   pop eax

   imul ebx, eax

   ret

;

return:

   mov ebx, 1

   ret

Now, that function calls itself with n = n-1 and pushes n every time until n = 0, when it multiplies all of them. Easy peasy

But now, that I have to call the function with (n-1) AND (n-2) I can't imagine how that would work, since I have to manage return addresses, the stack, the values. All I know that every time when it subtracts either 1 or 2 and the result is 1, then it should inc a counter which will then give us the result.

so return with n-1 until n-1 = 1, in which case return n-2 and then again n-1. I am just so confused and been struggling on this for the better of 2 days now.

Appreciate your help, thanks!

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

1

Write the code in a higher level language (or pseudo code) first, using named variables for temps. That way it'll be clearer what you need to do in the asm version.

– 500 - Internal Server Error
Nov 21 '18 at 11:04

add a comment |

I am having a hard time getting recursion to work. Well, recursion for a n! factorial calculator wasn't that hard, took me about half a day to figure it out.

   mov eax, [input]

   call factorialator



   jmp quit

 ;   

factorialator:

   cmp eax, 0

   je return

   push eax

   dec eax

   call factorialator

  ;

   pop eax

   imul ebx, eax

   ret

;

return:

   mov ebx, 1

   ret

Now, that function calls itself with n = n-1 and pushes n every time until n = 0, when it multiplies all of them. Easy peasy

so return with n-1 until n-1 = 1, in which case return n-2 and then again n-1. I am just so confused and been struggling on this for the better of 2 days now.

Appreciate your help, thanks!

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

1

Write the code in a higher level language (or pseudo code) first, using named variables for temps. That way it'll be clearer what you need to do in the asm version.

– 500 - Internal Server Error
Nov 21 '18 at 11:04

add a comment |

I am having a hard time getting recursion to work. Well, recursion for a n! factorial calculator wasn't that hard, took me about half a day to figure it out.

   mov eax, [input]

   call factorialator



   jmp quit

 ;   

factorialator:

   cmp eax, 0

   je return

   push eax

   dec eax

   call factorialator

  ;

   pop eax

   imul ebx, eax

   ret

;

return:

   mov ebx, 1

   ret

Now, that function calls itself with n = n-1 and pushes n every time until n = 0, when it multiplies all of them. Easy peasy

so return with n-1 until n-1 = 1, in which case return n-2 and then again n-1. I am just so confused and been struggling on this for the better of 2 days now.

Appreciate your help, thanks!

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

I am having a hard time getting recursion to work. Well, recursion for a n! factorial calculator wasn't that hard, took me about half a day to figure it out.

   mov eax, [input]

   call factorialator



   jmp quit

 ;   

factorialator:

   cmp eax, 0

   je return

   push eax

   dec eax

   call factorialator

  ;

   pop eax

   imul ebx, eax

   ret

;

return:

   mov ebx, 1

   ret

Now, that function calls itself with n = n-1 and pushes n every time until n = 0, when it multiplies all of them. Easy peasy

so return with n-1 until n-1 = 1, in which case return n-2 and then again n-1. I am just so confused and been struggling on this for the better of 2 days now.

Appreciate your help, thanks!

recursion assembly x86 nasm fibonacci

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

edited Nov 21 '18 at 8:31

Paul R

176k24298458

edited Nov 21 '18 at 8:31

Paul R

176k24298458

edited Nov 21 '18 at 8:31

Paul R

176k24298458

asked Nov 21 '18 at 8:21

Maritn Ge

166

asked Nov 21 '18 at 8:21

Maritn Ge

166

asked Nov 21 '18 at 8:21

Maritn Ge

166

1

Write the code in a higher level language (or pseudo code) first, using named variables for temps. That way it'll be clearer what you need to do in the asm version.

– 500 - Internal Server Error
Nov 21 '18 at 11:04

add a comment |

1

Write the code in a higher level language (or pseudo code) first, using named variables for temps. That way it'll be clearer what you need to do in the asm version.

– 500 - Internal Server Error
Nov 21 '18 at 11:04

Write the code in a higher level language (or pseudo code) first, using named variables for temps. That way it'll be clearer what you need to do in the asm version.

– 500 - Internal Server Error
Nov 21 '18 at 11:04

add a comment |

1 Answer
1

active

oldest

votes

It's the same principle. In the factorial case you save N temporarily because you need it later to multiply fact(N-1) by.
In the Fibonacci series case you also save N (or N-1) temporarily, because you need it later to calculate N-2 so that you can calculate fib(N-2).

An x86 implementaion might look like this:

fib:

    cmp eax,1       ; Base case?

    jbe done        ; Yes => return n

    dec eax

    push eax        ; Save n-1 on the stack

    call fib        ; Calculate fib(n-1)

    xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax

    dec eax

    call fib        ; Calculate fib(n-2)

    add eax,[esp]   ; fib(n-2) + fib(n-1)

    add esp,4       ; "Undo" the push operation

done:

    ret

answered Nov 21 '18 at 13:05

Michael

42.9k84594

1

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53407819%2frecursion-in-nasm-fibonacci%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

An x86 implementaion might look like this:

fib:

    cmp eax,1       ; Base case?

    jbe done        ; Yes => return n

    dec eax

    push eax        ; Save n-1 on the stack

    call fib        ; Calculate fib(n-1)

    xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax

    dec eax

    call fib        ; Calculate fib(n-2)

    add eax,[esp]   ; fib(n-2) + fib(n-1)

    add esp,4       ; "Undo" the push operation

done:

    ret

answered Nov 21 '18 at 13:05

Michael

42.9k84594

1

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

add a comment |

An x86 implementaion might look like this:

fib:

    cmp eax,1       ; Base case?

    jbe done        ; Yes => return n

    dec eax

    push eax        ; Save n-1 on the stack

    call fib        ; Calculate fib(n-1)

    xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax

    dec eax

    call fib        ; Calculate fib(n-2)

    add eax,[esp]   ; fib(n-2) + fib(n-1)

    add esp,4       ; "Undo" the push operation

done:

    ret

answered Nov 21 '18 at 13:05

Michael

42.9k84594

1

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

add a comment |

An x86 implementaion might look like this:

fib:

    cmp eax,1       ; Base case?

    jbe done        ; Yes => return n

    dec eax

    push eax        ; Save n-1 on the stack

    call fib        ; Calculate fib(n-1)

    xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax

    dec eax

    call fib        ; Calculate fib(n-2)

    add eax,[esp]   ; fib(n-2) + fib(n-1)

    add esp,4       ; "Undo" the push operation

done:

    ret

answered Nov 21 '18 at 13:05

Michael

42.9k84594

An x86 implementaion might look like this:

fib:

    cmp eax,1       ; Base case?

    jbe done        ; Yes => return n

    dec eax

    push eax        ; Save n-1 on the stack

    call fib        ; Calculate fib(n-1)

    xchg eax,[esp]  ; Place fib(n-1) on the stack, while retrieving n-1 into eax

    dec eax

    call fib        ; Calculate fib(n-2)

    add eax,[esp]   ; fib(n-2) + fib(n-1)

    add esp,4       ; "Undo" the push operation

done:

    ret

answered Nov 21 '18 at 13:05

Michael

42.9k84594

answered Nov 21 '18 at 13:05

Michael

42.9k84594

answered Nov 21 '18 at 13:05

Michael

42.9k84594

answered Nov 21 '18 at 13:05

Michael

42.9k84594

1

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

add a comment |

1

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

beware that xchg eax,[esp] has an implicit lock prefix, and thus is quite a lot slower than using separate load/store instructions (using a scratch register like mov edx,[esp] / mov [esp],eax / lea eax, [edx-1]). Of course if you cared about efficiency at all you'd compute Fib(n) iteratively with something like add eax,edx / add edx,eax in O(n) time instead of O(Fib(n)) time, as well as lower constant factors. But in general it's dangerous to show examples using xchg with mem.

– Peter Cordes
Nov 21 '18 at 17:06

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu