Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

About Recursion

Tags:
  1. Dec 22, 2015 #1
    I wrote a recursive function to calculate the number of the way for "horse" to move from one point to another in Chinese Chess in the following, but I cannot get the correct answer. My idea is to sum up the other 8(or less than 8) points' way toward the target. Thanks for any opinions in advance!
    Code (C):

    int ans(int orig_x, int orig_y, int tar_x, int tar_y, int place[][8])
    {
        int type[][2]={-1,2,1,2,1,-2,-1,-2,-2,-1,-2,1,2,1,2,-1};
        int next_x,next_y,a[8],b=0,i,j,count_last;
        place[orig_x+1][orig_y+1]=-1;
        place[tar_x+1][tar_y+1]=1;
        for(i=0;i<4;i++)
        {
            next_x=orig_x+type[i][0];
            next_y=orig_y+type[i][1];
            if(place[next_x+1][next_y+1]==1&&place[next_x+1][next_y+type[i][1]/abs(type[i][1])+1]!=2)
            {
                if(next_x==tar_x&&next_y==tar_y)
                {
                    count_last=0;
                    for(j=0;j<4;j++)
                    {
                        if(j=i+(i<2)*2-(i>1)*2)
                            continue;
                        if(place[next_x+type[i][0]+1][next_y+type[i][1]+1]!=1||place[next_x+1][next_y+type[i][1]/abs(type[i][1])+1]==2)
                            count_last+=1;
                    }
                    for(j=4;j<8;j++)
                    {
                        if(place[next_x+type[i][0]+1][next_y+type[i][1]+1]!=1||place[next_x+type[i][0]/abs(type[i][0])+1][next_y+1]==2)
                            count_last+=1;
                    }
                    if(count_last==7)
                        return 1;
                    else
                        a[i]=ans(next_x, next_y, tar_x, tar_y, place)+1;
                }
                place[orig_x+1][orig_y+1]=-1;
            }
            else
                a[i]=0;
        }
        for(i=4;i<8;i++)
        {
            next_x=orig_x+type[i][0];
            next_y=orig_y+type[i][1];
            if(place[next_x+1][next_y+1]==1&&place[next_x+type[i][0]/abs(type[i][0])+1][next_y+1]!=2)
            {
                if(next_x==tar_x&&next_y==tar_y)
                {
                    count_last=0;
                    for(j=0;j<4;j++)
                    {
                        if(place[next_x+type[i][0]+1][next_y+type[i][1]+1]!=1||place[next_x+1][next_y+type[i][1]/abs(type[i][1])+1]==2)
                            count_last+=1;
                    }
                    for(j=4;j<8;j++)
                    {
                        if(j=i+(i<6)*2-(i>5)*2)
                            continue;
                        if(place[next_x+type[i][0]+1][next_y+type[i][1]+1]!=1||place[next_x+type[i][0]/abs(type[i][0])][next_y+1]==2)
                            count_last+=1;
                    }
                    if(count_last==7)
                        return 1;
                    else
                        a[i]=ans(next_x, next_y, tar_x, tar_y, place)+1;
                }
                place[orig_x+1][orig_y+1]=-1;
            }
            else
                a[i]=0;
        }
        for(i=0;i<7;i++)
            b+=a[i];
        return b;
    }
     
  2. jcsd
  3. Dec 22, 2015 #2

    phinds

    User Avatar
    Gold Member
    2016 Award

    Have you stepped through it to see what it is doing? Do you know how to debug errors by stepping through a program?
     
  4. Dec 22, 2015 #3
    Yes, but I don't know how to check it in the recursion. I know the numbers in "place[][]"(the board) is correct, but how to check the recursive process?
     
  5. Dec 22, 2015 #4

    phinds

    User Avatar
    Gold Member
    2016 Award

    Why do you think stepping through a recursive process would not work? I do it all the time.
     
  6. Dec 22, 2015 #5

    harborsparrow

    User Avatar
    Gold Member

    Although I haven't read this code in great detail, I immediately see something about it that I don't like. The recursive call is near the end of the recursive function. I was taught (quite wisely) that the first thing a recursive function should always do is test and see if it's time to stop recurring and just return. The structure of this code is very confusing and definitely needs to be clarified--besides which, we don't really know what you are trying to accomplish.

    Frankly, you need comments in at least a few key places. And maybe some more descriptive variable names. This would help you, and help us help you.

    If the code is clarified and simplified, you should be able to dump out local variable contents to your GUI and verify that the recursive computation is occurring as you expected. Or else, use a debugger and painfully step through it. But personally, I advise you to rewrite the whole thing again first, with some comments and clarification about what all the different loops and sections are intending to do.
     
  7. Dec 22, 2015 #6

    QuantumQuest

    User Avatar
    Gold Member

    Being developer in C / Java for years, I want to ask why there is no single comment in the code. If you wrote it yourself, it would be a lot easier to add comments in some critical points, so any programmer inspecting it, would give help much easier. This would be great for yourself too, in case you revisit the code after some time. Guesswork in these cases, is not of much help. Everyone has his own way of writing code in any language and this is why comments exist.
    The simpler way to go through your program and see what it really does, is putting some "printf" statements to the appropriate places. Recursion is no different as phinds pointed out. Of course, there are many more advanced tools to test / debug your code, going through stepwise procedures, but I mention the one most primitive, if you will. Knowing what your recursion must do and maybe with the help of pen and paper if you need to, you can just compare results and see what is going wrong.
     
  8. Dec 22, 2015 #7

    phinds

    User Avatar
    Gold Member
    2016 Award

    I would like to add to what has already been said that due to lack of comments in your code, if you worked for me you would be in serious trouble. If you are a relatively inexperience coder, I could forgive the sloppiness of the code itself under the assumption that you are not yet quite there in terms of properly formed algorithms, but the lack of comments is inexcusable. I don't say this to be mean to you but to point out the importance of comments.

    I've been programming since 1962 and I can tell you ABSOLUTELY that lack of comments in code is just inexcusable and causes grief for everyone, including you.
     
  9. Dec 22, 2015 #8

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I agree with all the comments about comments. Here is one word of advice to a programmer -- If someone tells you that comments are not needed or that their code is "self-documenting", poke them in the eye. If they persist, poke them in the other eye.
     
  10. Dec 23, 2015 #9
    Yes, above, I realized. It is posted in hurry. I would try more and test. Thanks a lot again!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: About Recursion
  1. Recursion in C (Replies: 12)

  2. Recursion function (Replies: 5)

Loading...