Tree Recursion

• Linear Recursion : functions that calls itself only one time, such as in Tail or Head recursion.
• Tree Recursion : a function that is calling itself more than one time.

void fun(int n) {
  if (n > 0) {
    printf("%d", n);
    fun(n - 1);
    fun(n - 1);
  }
}

fun(3); // 3 2 1 1 2 1 1

• 15 calls are made for this particular function, when we pass the value as 3, which is equal to 2⁰ + 2¹ + 2² + 2³ = 2^(3 + 1) - 1. This is nothing more than something called the "GP series", or the sum of geometric progression terms. We can have this notation as O(2^n).

• 4 levels of recursion in this case

• Space complexity: depends on the maximum height of the stack. Same space was reused for calls; in tree recursion it is equal to O(n).