Tracing a recursive function

Discussion in 'Homework Help' started by zulfi100, Feb 29, 2016.

  1. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    I am tracing the following recursive function but i am going into an infinite loop. However when i run the function as a java program its generating an answer. The function is:
    static int fun(int i)
    {
    boolean res=false;
    if(i%2==1)
    res=true;
    else
    res=false;

    if ( res )
    return (i++);
    else
    return fun(fun( i - 1 ));
    }

    It has to be invoked using:

    fun(4):
    My steps of tracing are as follows:
    fun(4)
    = fun(fun(3))
    = fun(4)
    = fun(fun(3))
    = fun(4)

    Can somebody please tell me where i am making the mistake??

    Zulfi.
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,804
    If i happens to be 100, what is the value returned by the statement

    return (i++);
     
  3. RBR1317

    Active Member

    Nov 13, 2010
    232
    48
    While I am not a Java programmer, it does seem a little strange to call a particular function from within that function's own definition.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,804
    This is known as recursion and is a VERY common programming approach to many problems.

    A trivial example would be to find the factorial function using recursion:

    Code (Text):
    1.  
    2. int fact(int n)
    3. {
    4.    if (n < 1)
    5.       return 1;
    6.    return n * fact(n-1);
    7. }
    8.  
     
  5. MrAl

    Well-Known Member

    Jun 17, 2014
    2,440
    492
    Hi,

    What exactly are you trying to accomplish here?

    About Recursion...
    Yeah, recursive functions are common because sometimes the easiest way is to use recursion. Another example would be when parsing a file system for files and directories. If we call the function for the root directory it can then call itself whenever it encounters a sub directory, and thus gather all the file and directory names. If we did not do it that way we'd have to get all the directories first, creating a 'flat' list, then go through the list one at a time getting all the files. The recursive method is more elegant too. The function has to be written as a reentrant function so that it can hold previous values if needed. Just dont run out of stack space :)
     
  6. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
     
  7. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Thanks WBahn, I am able to solve this problem. Thanks Mr AI for your explanation and a very useful example.

    Actually, I am trying to generate the output of recursive function manually. I am calling it Tracing. I saw this method in a book and then i downloaded few recursive methods & tried to apply the method on them. I was able to run only one correctly. Rest were giving me problems. But now things are clear.

    Fun(4)

    = fun(fun(3))

    = fun(3): Note return (3++) would return 3 and not 4

    = 3
    Zulfi.
     
  8. WBahn

    Moderator

    Mar 31, 2012
    17,777
    4,804
    Good, you got it!

    What you are doing goes by a number of names. Tracing is one of them. It is also called desk-checking and several others. It's an extremely valuable method both for learning how an algorithm works and also for figuring out why an algorithm doesn't work.
     
Loading...