Recursion - notes-archive/DSA GitHub Wiki

Intro to recursion

What is recursion?

Recursion : A function calling itself directly or indirectly.

Directly:

void fun1(){
    //somecode ...
    fun1();
    //some other code...
}

Indirectly: Not a very common approach (Mostly direct recursive approach is used)

fun1() -> fun2() -> fun1()

void fun1(){
    //somecode ...
    fun2();
    //some other code...
}
void fun2(){
    //somecode ...
    fun1();
    //some other code...
}
  • If you dont add a base case, recursion never stops and we might end up with stackoverflow(in case of java) or segmentation fault error(in case of cpp).
  • There should be one stopping condition atleast. Such stopping conditions are called Base cases

Example:

void fun1(int n)
{
    //Base Case
    if (n == 0)
        return;
    cout << "Function 1" << endl;
    fun1(n - 1);
}
int main(int argc, char const *argv[])
{
    /* code */
    fun1(2);
    return 0;
}

Typical structure of a recursion

(Assuming: You are not using global vars or some other tricks to stop recursion ).

returntype function(parameters){
    Base cases
    //some other code.....
    Recursive call (i.e., call to function()) with atleast one change in parameters
    //some other code...
}

Applications of recursion

Any problem which can be solved iteratively can also be solved using recursively and vice-versa. They both have same expressive power.

Now the question is if we can write equivalent iterative code for every recursive code or vice versa, where do we use recursion?

  • Many algorithm techniques are based on recursion.

    • Dynamic programming
      • In DP, generally first solution is to write a recursive solution. If we see overlapping subproblems (apply memoization or tabulation), we use DP to optimise it.
      • Example: Finding diff between two files (solved using LCS approach)
    • Backtracking
      • These problems are inherently recursive in nature.
        • Example : Rat in a maze, n-queens problem. (Its easy to write recursive solns than iterative for problems like this)
    • Divide and conquer
      • Examples: Binary search, quicksort and mergesort

  • Many problems which are inherently recursive (Easy to write recursive than iterative)

    • Towers of Hanoi
    • DFS based travels
      • Of Graphs
      • Inorder, preorder postorder traversals of tree
      • Searching for a file in your pc - solid example of DFS

  • Cons of recursion

    • (Auxillary) space complexity increases
    • Function call overhead.

  • Pros:

    • Easy implementation

Examples

void fun1(int n)
{

    if (n == 0)
        return; //Base Case
    cout << n << endl;
    fun1(n - 1);
    cout << n << endl;
}
int main(int argc, char const *argv[])
{
    /* code */
    fun1(3);
    return 0;
}
//Output : 321123

void fun1(int n)
{

    if (n == 0)
        return; //Base Case
    fun1(n - 1);
    cout << n << endl;
    fun1(n - 1);
}
int main(int argc, char const *argv[])
{
    /* code */
    fun1(3);
    return 0;
}
//Output : 1213121

int fn(int n)
{
    if (n == 1)
        return 0;
    else
        return 1 + fn(n / 2);
}
//TC: O(floor(logn base2))
//SC: O(n/2)
//fn(16) -> O/p: 4 => (1+f(8)) ->(1+1+f(4)) ->(1+1+1+f(2)) -> (1+1+1+1+f(1))
//fn(20) -> o/p: 4 =>(1+f(10)) -> (1+1+f(5)) -> (1+1+1+f(2)) -> (1+1+1+1+f(1))
//fn(19) -> o/p:4 => (1+f(9)) -> (1+1+f(4)) -> ->(1+1+1+f(2)) -> (1+1+1+1+f(1))

//output remains same until we get to next power of 2.

Binary representation of a number(n > 0) using recursion

int fn(int n)
{
    if (n == 0)
        return;
    fn(n / 2);
    cout << n % 2 << endl;
}
//TC:

print 1 to N using recursion

private static void fn(int n) {
    if (n == 0)
        return;
    fn(n - 1);
    System.out.println(n);
}//TC; O(n) AS: O(n+1)

print N to 1 using recursion

private static void fn(int n) {
    if (n == 0)
        return;
    System.out.println(n);
        n(n - 1);
}// TC: theta(n)
//SC: (Auxillary space) : O(n)
  • Note: We can reduce the auxillary space using tail recursion.
    • The above fn takes less time on modern compilers because of tail recursion

Tail Recursion

To understand tail recursion, lets take a closer look at these 2 functions.

//prints from n to 1
void fn1() {
    if(n==0) return;
    System.out.println(n);
    fn1(n-1);
}
//this function takes lesser time

//prints from 1 to n
void fn2(){
    if(n==0) return;
    fn2(n-1);
    System.out.println(n);
}

Can you guess the reason why would 1st function take lesser time to compile on modern compilers?

If you look at the call stack of fn1()

+__fn1(3)
    |__ 3
    |__fn1(2)
        |__ 2
        |__ fn1(1)
            |__ 1
            |__ fn1(0)

When fn1(0) finishes, control returns back to fn1(1), fn1(1) doesnt have anything to do it finishes immediately. This is where tail recursion comes into picture.

A function is called Tail recursive when the parent function has nothing to do when the child finishes the call.

This is not the case with fn2(3). When fn2(0) returns to its parent fn2(1), it still has got work to do (print the output).

In very simple words

A function is called tail recursive, when the last thing that happens in the function is recursive call and nothing happens after that.

What are the pros of this?

The point is your caller doesn't have to save the state, generally what happens in recursive calls is, caller's state is saved then called function is called and once the called function is finished then the caller resumes its function from the same point. We dont need to resume the execution here at all, there's no point in resuming the execution and thats what the optimisation modern compilers do.

When modern compilers see tail recursive functions they replace the above code with

void fn1() {
    //compiler adds this label
    start:
        if(n==0) return;
        System.out.println(n);
        // and replaces the line fn1(n-1) with below statements
        n= n-1 ;
        goto start;
}

These changes that modern compilers make are called Tail call elimination

Now, the question arises is when given a non tail recursive code, can we convert it tail recursive?

Lets have a look at the below examples.

//prints from 1 to n
void fn2(){
    if(n==0) return;
    fn2(n-1);
    System.out.println(n);
}

//Tail recursive version of the code
//initially pass k = 1
void fn2(int n, int k){
    if(n==0) return;
    System.out.println(k);
    fn2(n-1,k+1);
}

Can we convert every non tail recursive to tail recursive by adding few parameters?

No. Consider merge sort and quick sort, if you take a closer look at these two algorithms, quick sort is tail recursive and merge sort is not. This is one of the reasons, quick sort is fast.

In case of tree traversals (Inorder,preorder and postorder), you can notice that preorder traversal and inorder traversal are tail recursive, but post order traversal is not, thats why when you are given a problem and if you can choose any of the traversals, you should prefer either inorder or preorder over the postorder.

Is this tail recursive?

int factorial(int n){
    if(n==0 || n== 1) return 1;
    return n * factorial(n-1);
}

No. The reason is recursion is not the last thing that happens in this function. When you call factorial(n-1) you need to know the result of that function and multiply it with n and then it need to return. Parent call doesn't finish immediately after the child call, its going to use the result of child call and then multiply the result with n after that its going to return.

Equivalent tail recursive code

//initially pass k = 1
int factorial(int n, int k){
    if(n==0 || n== 1) return k;
    return factorial(n-1,k*n);
}

Few problems on recursion worth looking at: