Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Double Recursion

user04user04 Member Posts: 7
So I have a problem with my current task...it involved double recursion. Here's the code snippet in C.

[code]
long unsigned chaos( int arg )
{
if ( arg <= 2){
return 1;
else{
return chaos( arg - chaos ( arg - 1) ) + chaos ( arg - chaos (arg - 2 ) );
}

}

[/code]

I understand that I have to utilize the stack a lot here, but the more and more I push on the stack, the more I have to pop off, which is causing garbage as my output?

Any suggestions?

Thannks

Comments

  • stoberstober Member Posts: 9,765 ✭✭✭
    chaos certainly is an approproiate name for that function! The number of recursive calls seems to go up expotentially as the initial value of arg increases.

    5 -- 25
    6 -- 49
    7 -- 93
    8 -- 161
    9 -- 281

    Let your C compiler generate the assembly code so that you can see how it is done.
  • user04user04 Member Posts: 7

    : Let your C compiler generate the assembly code so that you can see how it is done.
    :


    I don't have a C compiler at my home box...that was a code snippet from the assignment. :-(
  • DariusDarius Member Posts: 1,666
    : So I have a problem with my current task...it involved double recursion. Here's the code snippet in C.
    :
    : [code]
    : long unsigned chaos( int arg )
    : {
    : if ( arg <= 2){
    : return 1;
    : else{
    : return chaos( arg - chaos ( arg - 1) ) + chaos ( arg - chaos (arg - 2 ) );
    : }
    :
    : }
    :
    : [/code]
    :
    : I understand that I have to utilize the stack a lot here, but the more and more I push on the stack, the more I have to pop off, which is causing garbage as my output?

    YOU don't really need to utilize the stack more, your code will. All you ever need to use the stack for is to preserve values. The only value you need to preserve is arg. So, you can make the code using only one push/pop. Actually you don't even need the pop as all it will be there for is to clean up the stack, you could use add (e)sp, 2 (4), or simpler ret 2 (4). If you pass parameters on the stack then you don't need any special pushes or pops (though now you'll need them to pass the arguments, but those would be mechanical.)

    "We can't do nothing and think someone else will make it right."
    -Kyoto Now, Bad Religion

  • ChojinChojin Member Posts: 39
    try to see if there is another way of doing it not by recursion ;
    but you are geting garbage is because you dont have implement the function ritgh .

    try to think as the compiler or see who the compiler solve that func ..

    But i think C solves the procedure as this ::

    parameter are passed by the stack
    and return the eax .

    ex :

    Myfunc ( arg 1 , arg2 , arg3 )

    push arg3
    push arg2
    push arg1
    call MyFunc

    for double recursion i think that you have to solve first one parte and then go to the other ;






  • Andre YoungAndre Young USAMember Posts: 0

    _______ ( http://forcoder.org ) free ebooks and video tutorials about ( MATLAB C++ Scratch PHP R Java Delphi Python JavaScript Visual Basic C# Ruby Objective-C Assembly PL/SQL Perl Swift Go C Visual Basic .NET Dart Awk Prolog Alice Scheme VBScript FoxPro Rust Scala Ada LabVIEW SAS Lisp COBOL Erlang Transact-SQL Bash Kotlin Fortran Crystal Clojure Logo Lua F# Apex Hack ABAP Julia ML D ) ______________

Sign In or Register to comment.