You are here:

Java/Using Recursion to fill call trees

Advertisement


Question
Hi Artemus,

I have a question regarding a recursion function and how it can be used to fill a call tree. I have a method below which is being called with func2(3), i'm looking to use the information from this method to the following call tree:

http://img845.imageshack.us/img845/2509/sg2w.jpg

[/code]
public class callTree {
  public static void main(String[] args) {
     System.out.println (func2(3));
  }

  public static int func2(int num)
       {
         System.out.println(num);
     if(num <= 0)
       {
     return 1;
  }
     else
     {
        return func2(num-2) + func2(num-1);
     }
     
  }

[code/]
I have added the print statement above the if condition to see how the recursion function is working. if i just try to plug in the value of 3 into the function then i would get outputs such as
(3-2)=1 & (3-1)=2 <---would these two values plug into the tier 1 of the call tree?

if the above is correct then the subsequent output for the following would be: (1-2)=-1 & (1-1)=0, (2-2)=0 & (2-1)=1

if the above is correct then the call tree would look something like this?

http://img850.imageshack.us/img850/4799/veiy.jpg

does this seem correct?

Thank you for you're time

Answer
Your logic seems good. The calls happen midway though the calculation, so the calculation is held off until those are evaluated.

The output of the final method would be the total number of nodes in the tree. Since once you reach a leaf, 1 is returned regardless of whether 0 or -1 was passed in.

Java

All Answers


Answers by Expert:


Ask Experts

Volunteer


Artemus Harper

Expertise

I have a Masters in computer science. I can answer questions on core J2SE, swing and graphics. Please no questions about JSP or J2ME.

Experience

I have experience in Core Java, good background in Java swing/gui, some experience with JNI, Java reflection. Some experience in bio-informatics. Basics in c++ and c#

Organizations
Washington State University

Education/Credentials
MS in Computer Science from Washington State University and a BS in Mathematics and Computer Science from Central Washington University.

©2016 About.com. All rights reserved.