Recursion Basic : Part 1

if you are learning programming language and have already hands on with the fundamentals and want to further improve your problem solving skills with DSA hands on with that programming language recursion is one of the topic which very very important, we are going to understand recursion using Java.

if you have very clear understand of how recursion works you can understand the concepts like linked list, binary tree etc. very easily and solve problems like binary search, merge sort, quick sort and lot other very easily.

What is Recursion ?

a function which calls itself with simpler version of itself is called recursion.

remember simpler version of itself.

we create a recursive function such that at a certain point that recursion should stop with the known conditions giving us the desired result we want, otherwise it’s going to going call itself infinitely

what happens if the function call itself infinitely ?

let’s understand this with simple example with an print(n) function which call itself recursively with subtracting one number for n value every time it call itself

public class PracticeApplication {
   public static void main(String[] args) {
      SpringApplication.run(PracticeApplication.class, args);
      print(10);
   }

   public static void print(int n){
      System.out.println("count"+ n);
      print(n-1);
   }

}

Output :

2023-11-12T19:14:49.481+05:30  INFO 18017 --- [           main] c.e.P.PracticeApplication                : Started PracticeApplication in 0.729 seconds (process running for 0.902)
count10
count9
count8
count7
.
.
.
count-11197
Exception in thread "main" java.lang.StackOverflowError
 at java.base/java.lang.System$2.encodeASCII(System.java:2453)
.

YUP, if we call itself infinitely there will come a point where there is no memory available to further process the recursive call.

But why are we getting the StackOverflowError and how to prevent infinite recursion and what’s it got to do with memory isn’t it’s just a normal method call repeatedly?

as we know whenever we run main method in a Main class in java that method call is added in stack memory of JVM with all it’s method specific variable,

similarly when we call the print() method with n=10 that call is also added in the stack and next time when that same function call itself with different argument value i.e n=9 similar call is added in the memory

so if the function call itself infinitely the calls are going to stack up in the stack memory until the stack memory cannot handle any more recursive call and hence it throw an error StackOverflowError stating it memory is overflowing that what it can handle.

So how to stock infinite recursion call ? simple, we put the condition where it break out of that recursive loop and stops the recursion, how ?

in above print(int n) inside the body if we put the condition so that when the number reaches the value 0 we stop the recursion i.e. there will be no further recursion call and that condition is called as a base condition and that recursion is called a base case.

public static void print(int n){
      //base condition
      if(n==0){
        return;
      }
      System.out.println("count"+ n);
      print(n-1);
}

Note : whenever a function call itself recursively the current call method call stays in the stack until it’s recursive call is completed and control of execution flow is returned back to current method call and once the current method call execution is completed then current method call memory is released from the stack memory

the same recursive calls can be represented in iterations and vice versa is also true,

Does it mean recursion is better approach that iterations ?

No working with recursion is not always the most efficient approach, as we have seen every recursive call is added in the stack and hence adding the memory overhead for each call unlike a iteration where there is no extra method call method is added

there are time when working with recursion gives better results than iterations and there are some times when working with iteration give better results

we can understand this with an fibonacci number example, below there are two function one finds nth fibonacci number recursively and other one finds it using normal iteration, let’s find out how much time it find result for each of them

public class PracticeApplication {

 public static void main(String[] args) {
    SpringApplication.run(PracticeApplication.class, args);
    int t1 = LocalTime.now().getSecond();
    int rec = fibRecursive(47); // recursive call
    int t2= LocalTime.now().getSecond();
    int itr = fibIteration(47); //iterative call
    int t3 = LocalTime.now().getSecond();
  
    System.out.println("rec : "+rec+", time : "+(t2-t1)+" sec");
    System.out.println("itr : "+itr+", time : "+(t3-t2)+" sec");
 }

//Recursive Function
 public static int fibRecursive(int n){
    if(n<=1) return n;
    return fibRecursive(n-1)+fibRecursive(n-2);
 }

//Iterative Function
 public static int fibIteration(int n){
    int pre = 0;
    int curr = 1;
    for(int i=2; i<=n; i++){
     int temp = curr;
     curr = curr + pre;
     pre = temp;
    }
    return curr;
 }

Output :

2023-11-12T20:17:24.265+05:30  INFO 18664 --- [           main] c.e.P.PracticeApplication                : Started PracticeApplication in 0.72 seconds (process running for 0.874)
rec : -1323752223, time : 7 sec
itr : -1323752223, time : 0 sec

as you can see the time it took for recursive function to find 47th fibonacci number is 7 sec and against this iterative function can find the answer instantly.

Note : if you are wondering why negative result, it’s because the value is going above integer range

that’s why we have to remember the purpose of using recursion when we want to use it, i.e. to recursion helps in writing shorter and easier solution for complex problems

Note : space complexity for the recursive calls is not constant

How to Approach a Recursive Problem ?

to find whether the problem can be solved using recursion just follow the below steps.

1. Identify if you can break down the problem in smaller problems.

ex. you can write a function to find the factorial of a number using recursion, and the the recursive factorial problem function can be simplified as

(5!) can be simplified as (5 * 4!) then again (5*4*3!) and so on till (5*4*3*2*1).

and can be represented in formulae as

f(n) = n * f(n-1)

base condition n=1 return 1

this formulae is called as Recurance Relation can be written for any recursive function.

finding the recurance relation can also help you solve problem very easily.

2. Understand what’s the Base condition to break the recursion

3. find the argument which is necessary to simplify the next recursive call

4. Draw Recursion Tree

one of the most challenging thing people face is to understand the flow of recursive call, and to solve the this issue is dry run the problem using pen and paper and believe me unless you start to write the recursion tree using pen and paper recursion can become very tough to understand

if we look at the fibonacci series example for 4th value we can draw the recursion tree as

here we know the value of f(0)=0 and f(1)=1 which is known value which can be used to write the base condition to break the recursion.

IMP : always remember that recursive call are executed from left to right and hence the result are are added from bottom left all the way till left branch is done and then towards right here as well left side branches are executed first.

5. Use Debugger to understand how call are added in stack memory and how they are removed.

if you follow above 5 steps then solving and understanding can become very easy for you, but off course you have to practice the recursion problem to master the recursion.

So, Can I write recursive call in function anywhere we want ?

here it can be little tricky the order in which you call the function can definetely affect you function.

let’s understand this with an example, observer below example and try to guess the result

// n=5
public static void print(int n){
      if(n==0) return;

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

calling this function from main method.

if you have guessed it as ( 5,5,4,4,3,3,2,2,1,1,) then you are wrong like other function call in java after executing first print statement your method will wait for recursion call to complete then execute the next print statement

in recursion call again same thing is follow until the recursion ends and control is given back to calling method, hence the output is (5,4,3,2,1,1,2,3,4,5)

Recurance Relation

recurance relation can be of different types

1. Linear Recurance Relation (Very Ineffective like in Fibonacci series)
2. Divide and Conquer Recurance Relation (like in binary search)

sometimes it’s best choice that once you find the recursive solution you convert the recursive solution to iterative solution so as to get the best result in achieve better time and space and space complexity.

Anything left ?

you have see some of the above recursion and in these example some recursion has the statement execution and some like fibonacci series example has a recursion call

the which does not have the recursion call at the end is called a tail recursion.

Thanks for reading this block, you can check out my other blogs.