# 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
18,080
4,917
If i happens to be 100, what is the value returned by the statement

return (i++);

3. ### RBR1317 Active Member

Nov 13, 2010
264
54
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
18,080
4,917
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 Distinguished Member

Jun 17, 2014
2,548
514
Hi,

What exactly are you trying to accomplish here?

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

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
18,080
4,917
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.