Recursion

recursion

rɪˈkəːʃ(ə)n/

noun

MATHEMATICSLINGUISTICS

noun: recursion

1. the repeated application of a recursive procedure or definition.

   • a recursive definition.

     plural noun: recursions

Basically recursion is doing something repeatedly. In programming recursion is an act of calling itself in the function/ method scope.

Think of a program where you want to count down from any given number. As an example if we input 10 then it should count from 3 to 0. We can do this using a recursive function.

class Recursion{
    public static void main(String args[]){
  count(3);
}
public static void count(int n){
System.out.println(n);
count(n-1);
  }
}

The function/method count, prints n taken as its parameter and call the count method again.

The output will be:

3
2
1
0
-1
-2
-3
-4
-5
...
..-
...




The method call itself recursively, so that there will be no end. It creates infinite calls and ultimately the system will get crashed. To make the real use of recursive functions, we need to give one or more conditions where it should stop calling itself and return to the place where it was called.

class Recursion{
  public static void main(String args[]){
count(3);
}
public static void count(int n){
System.out.println(n);
if (n<=0){
return;
}
count(n-1);
}
}

This count method will not call it self, if n is a negative number or zero.

So the output will be,
3
2
1
0











The n, is a local variable where its value is determined by the argument passes when the count method is being called. Since n is an integer, which is a primitive data type, only the value is passed to the recursive call. n's value is stored locally in its method, so each count method call has its n stored separately for each. As example lets print n's value after the function call.

class Recursion{
  public static void main(String args[]){
count(3);
System.out.println("end");
}
  public static void count(int n){
System.out.println(n);
if (n==0){
return;
}
count(n-1);
System.out.println(n);
}
}

output of this program will be,
3
2
1
0
1
2
3
end










Since the return statement inside the if condition is before the last print statement, 0 will not print twice. When returning each n's value stored in each method will be printed.

Think of the below program which add all the integers from 0 to any given positive number.

class Recursion{
public static void main(String args[]){
System.out.println(sum(3));
}
public static int sum(int n){
if (n<=0){
return 0;
}
return n+sum(n-1);
}
}

the sum method accepts integer value as parameter and returns the sum.

The output of this program will be,

6

















But as you can see, until the last return statement, all the n values are temporarily stored in each method's return statement. If we want the sum of all integers up to 1000, then we have to keep all the 1000 integers in the ram which is a waste of space. As a solution we can use the tail recursion style which is more effective in such cases.

class Recursion{
  public static void main(String args[]){
System.out.println(sum(3));
}
public static int sum(int n){
return _sum(n,0);
}
private static int _sum(int n,int sumN){
if (n==0){
return sumN;
}
return _sum(n-1,sumN+n);
}
}

The _sum method calculate the sum each time when the method is called, unlike before where calculation is done at last.

The output of this program is,

6

















But this method is much more faster than the previous when it comes to large calculations.


Recursion is a powerful feature of a programming language. It has its own advantages and disadvantages depending on the programming language we are using. Recursion can be best used with functional programming languages or scheme programming languages rather than other imperative languages.