Tracing a recursive function

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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.
 

RBR1317

Joined Nov 13, 2010
713
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.
 

WBahn

Joined Mar 31, 2012
29,976
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.
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:
int fact(int n)
{
   if (n < 1)
      return 1;
   return n * fact(n-1);
}
 

MrAl

Joined Jun 17, 2014
11,389
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.
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 :)
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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 :)
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
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.
 

WBahn

Joined Mar 31, 2012
29,976
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.
 
Top