• 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);
……….
……….
}
}
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);
}
}
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.