Double Recursion

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

  • 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.

  • : 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. :-(
  • : 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

  • 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 ;






Sign In or Register to comment.

Howdy, Stranger!

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

Categories