Recursion

Question 1

Time complexity formula for recursive code?

Answer 1

Simple case with one branch:
O(number of recursive calls * work per recursive call)
Complex case:
O(branching_factor^max_depth(height) * work per recursive call)
Proportional to # leaf nodes in
complete tree

Question 2

Space complexity for recursive code?

Answer 2

O(depth_of_recursion * space_per_recursive_call)

Proportional to the depth of the recursion

Question 3

What are 6 recursive patterns?

Answer 3

1. Iteration
2. Breaking into sub problems
3. Selection(combination)
4. Ordering(Permutation)
5. Divide and conquer
6. Depth first search

Question 4

3 ways to return results from recursive function?

Answer 4

1. Store the result to global variable
2. Store the result to a passed variable
3. Build up the result as we return.

Question 5

In recursive function , can we reassign a reference and expect it to propagate back to the call stack?

Answer 5

No

https://stackoverflow.com/questions/7848312/recursive-pass-in-object-by-reference-java

Question 6

How to Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

Answer 6

public double MyPow(double x, int n)
        {
            long pow = n;
            if (n < 0)
            {
                x = 1 / x;
                pow = -pow;
            }
            return Helper(x, pow);
        }      

    private double Helper(double x, long n)
    {
        if (n == 0)
            return 1;
        if (n == 1)  //! power of 1 of any number is equal to that number 
            return x;

        if (n % 2 == 0) 
            return Helper(x * x, n / 2);            
        else 
            return x * Helper(x * x, n / 2);
    }

Question 7

How to implement gcd recursively ?

Answer 7

public static int gcd(int a, int b) {
if (b > a) return gcd(b, a);
if (b == 0) return a;
return gcd(b, a % b);
}