DEV Community

Cover image for Java: Recursion Basics. 🔁
Raksha Kannusami
Raksha Kannusami

Posted on • Updated on

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();
}
Enter fullscreen mode Exit fullscreen mode

When a function calls itself indirectly:

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

void function2(){
    .
    .
    function1();
}
Enter fullscreen mode Exit fullscreen mode

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);
}
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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! 🌸

Top comments (3)

Collapse
 
ashishshetty profile image
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

Collapse
 
rakshakannu profile image
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!

Collapse
 
ashishshetty profile image
AlphaSierra

Oh no problem. Happy to help 👍