Skip to main content

Tree Recursion

 • If a recursive function calling itself more than one time then it is tree recursion

syntax : 

fun(n) { 
if( n > 0 ) {
 ………..
 ……….. 
……….. 
……….. 
 fun(n -1);
 ……….. 
……….. 
 fun(n-1); 
………. 
………. 
 } 
}

Example-:

class Test{
   public static void fun(int x){
     if(x>0){
        System.out.print(x);
        fun(n-1);
        fun(n-1);
    }
}
public static void main(String[] args){
    fun(3);
}
}




Output-: 3 2 1 1 2 1 1

total number of functions call


fun(3) call 1time
fun(2) call 2 time
fun(1) call 4 time
fun(0) call 8 time

sum of calls-:
1+2+4+8=15
or
20+21+22+23=23+1-1        formula of GP series is 20+21+22+23........+2n=2n+1-1
Time complexity is O(2n)
Space complexity is O(n)

On Time Efficiency

Tree recursive procedures typically take exponential time to compute. Why would we ever use them?

  • Some problems are more easily solved by thinking tree recursively. Try writing count-change using for loops in another language.
  • Some issues are intractably hard, meaning the fastest known algorithms we have for them are still exponential in runtime.
  • Turns out, we can optimize tree recursive procedures without changing their shape, which we will cover later in the course.

Popular posts from this blog

Java

Codes With Java — Basics Codes With Java Java tutorials & fundamentals About Contact Privacy Basic Fundamentals Java source file structure Import Statement Static Import Packages Data Type Variables Final Variable Declaration and Access Modifier Inner classes applicable modifiers Static Modifier Synchronized Native Transient Volatile Interface Introduction Interface Declaration and Implementation Interface methods and variables Naming Conflicts Interface Marker interface and Ad...
Read more

Short Circuite Operators part 4

                                                             Short Circuit Operators In  Java logical operators , if the evaluation of a logical expression exits in between before complete evaluation, then it is known as  Short-circuit . A short circuit happens because the result is clear even before the complete evaluation of the expression, and the result is returned. Short circuit evaluation avoids unnecessary work and leads to efficient processing. 1-: AND(&&) 2-:OR(||) these are exactly same as bitwise operators (&,|) except the following differences. Single Short Circuit Operator(&,|) Both arguments Should be evaluated always. relatively performance is low. Applicable for both boolean and Integral types. Double Short Circuit Operator(...
Read more

Operators & Assignment part 3

                                                                                       Operators & Assignment 1-:instanceof Operators 2-:Bitwise Operators                                                                        instanceof Operators we can use instanceof operator to check whether the given object is of a particular type are not. Example-: /* list is a collection of objects. List l=new List(); l.add(Customer); l.add(Student); l.add(Test); Object o=l.get(...
Read more