Java: Recursion Basics. 🔁

What is recursion?

Recursion is a way to write a program where the function calls itself. A function is called recursive if it calls itself directly or indirectly.

When a function calls itself directly:

void function1(){
    .
    . 
    function1();
}

When a function calls itself indirectly:

void function1(){
    .
    .
    function2();
}

void function2(){
    .
    .
    function1();
}

Applications of recursion:

🎯 Dynamic programming
🎯 Backtracking
🎯 Searching algorithms like Binary search
🎯 Sorting algorithms like merge sort and quick sort
🎯 Tree traversals ... etc.

Is recursion better than iteration?

Even though recursion might look like its better than iteration since the length of the code is less, it is the iteration that is always efficient when it comes to the time complexity of the code. This is because, when recursive code is being compiled, the number of arguments in the function call stack increases and this increases the time complexity of the code.

Printing 1 to N using Recursion

class Test{
  static void print1toN(int n)
  {
    if(n==0)
      return;
    print1toN(n-1);
    System.out.print(n+" ");
}

public static void main(String[] args)
{
  int n=10;
  print1toN(n);
}
}

Printing N to 1 using Recursion

class test{
  static void printNto1(int n)
  {
    if(n==0)
      return;

    System.out.print(n+" ");
    printNto1(n-1);
  }
}

public static void main(String args[])
{
  int n=10;
  PrintNto1(n);
}

Some Recursive problems to explore:

Basic Problems:

1. Fibonacci series using recursion
2. Sum of natural numbers using recursion
3. Palindrome check using recursion
4. Sum of digits using recursion

Advanced Problems:

1. Tower of Hanoi
2. Rod cutting problem
3. Josephus problem

To get good at recursion, practice is the key. After a significant amount of practice, you'll easily recognize the questions that you can solve using recursion!

To start off, you can practice the above-listed problems on GeeksforGeeks or Leetcode. 👩🏻‍💻

... to be continued 🎉

keep learning, keep coding! 🌸

Comments

[AlphaSierra]

Shouldn't the indirect recursion be something like this:

void function1(){
    .
    .
    function2();
}

void function2(){
    .
    .
    function1();
}

Also Would like to point out the slight error in the 1 to N logic, unless I am wrong it should look something like this:

public class Test{
   static int x = 1;

   static void print1toN(int n)
   {
      if(x>n)
         return;
      System.out.print(x+" ");
      x++;
      print1toN(n);
   }

   public static void main(String[] args)
   {
      int n=10;
      print1toN(n);
   }
}

Other than these things, interesting topic, keep it up...v

[Raksha Kannusami]

Thank you for pointing out the typo!
and regarding the print 1 to N, problem, I did not focus on the base cases, I just wanted to show how recursion works!

[AlphaSierra]

Oh no problem. Happy to help 👍