Recursive Methods
Recursive Methods
What is Recursive Function?
A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration.
Example of a recursive function.
function Count (integer N)
if (N <= 0)
return "Must be a Positive Integer";
if (N > 9)
return "Counting Completed";
else
return Count (N+1);
end function
Note: The function Count() above uses recursion to count from any number between 1 and 9, to the number 10. For example, Count(1) would return 2,3,4,5,6,7,8,9,10. Count(7) would return 8,9,10. The result could be used as a roundabout way to subtract the number from 10.
public class RecSeries
{
public static void main(String[] args)
{
RecSeries r=new RecSeries();
System.out.println("Series using Recursive Function :");
r.Count(3);
}
void Count (int N)
{
if (N <= 0)
{
System.out.print("Must be a Positive Integer");
return;
}
if (N > 9)
{
System.out.print("Counting Completed");
return;
}
else
{
System.out.print(N+ " , ");
Count (N+1);
return;
}
}
}
C:\>javac RecSeries.java
C:\>java RecSeries
Series using Recursive Function :
3 , 4 , 5 , 6 , 7 , 8 , 9 , Counting Completed
Recursive functions are common in computer science because they allow programmers to write efficient programs using a minimal amount of code.
The downside is that they can cause infinite loops and other unexpected results if not written properly.
For example, the function is terminated if the number is 0 or less or greater than 9.
If proper cases are not included in the function to stop the execution, the recursion will repeat forever, causing the program to crash, or worse yet, hang the entire computer system.
Every recursion should have the following characteristics.
1. A simple base case which we have a solution for and a return value.
2. A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
3. A recursive call which passes the simpler problem back into the method.
class SimpleFact
{
public static void main(String[] args)
{
SimpleFact s=new SimpleFact();
System.out.println(s.factorial(5));
}
int factorial(int n)
{
return n * factorial(n - 1);
}
}
A classic example of recursion
For example, factorial(5) is the same as 5*4*3*2*1, and factorial(3) is 3*2*1.
Actual factorial function
class FactUsingRecursive
{
public static void main(String[] args)
{
FactUsingRecursive obj=new FactUsingRecursive();
int f=obj.myFactorial(5);
System.out.println("Factorial of 5 is :"+f);
}
int myFactorial( int integer)
{
if( integer == 1)
return 1;
else
{
return(integer*(myFactorial(integer-1)));
}
}
}
C:\>javac FactUsingRecursive.java
C:\>java FactUsingRecursive
Factorial of 5 is :120
The problem with this function, however, is that it would run forever because there is no place where it stops. The function would continually call factorial. There is nothing to stop it when it hits zero, so it would continue calling factorial on zero and the negative numbers. Therefore, our function needs a condition to tell it when to stop.
Since factorials of numbers less than 1 don’t make any sense, we stop at the number 1 and return the factorial of 1 (which is 1). Therefore, the real factorial function will look like this:
Actual factorial function
int factorial(int n)
{
if(n == 1)
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}
Call of Recursive Function
class FactUsingRecursive
{
public static void main(String[] args)
{
FactUsingRecursive obj=new FactUsingRecursive();
int f=obj.rec(5);
System.out.println("Factorial of 5 is :"+f);
}
int rec( int x)
{
int f;
if( x == 1)
return 1;
else
{
f=(x*(rec(x-1)));
}
return f;
}
}
Basic steps of recursive programs
Every recursive program follows the same basic sequence of steps:
1. Initialize the algorithm. Recursive programs often need a seed value to start with. This is accomplished either by using a parameter passed to the function or by providing a gateway function that is nonrecursive but that sets up the seed values for the recursive calculation.
2. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.
6. Return the results.
Example of Fibonacci using Recursion
class FibonSeries
{
public static void main(String[] args)
{
FibonSeries f=new FibonSeries();
System.out.println( "Fibonacci series using Recursion : ");
int initial_value=0,final_value=1,count=10;
f.fibo_gen(initial_value,final_value,count);
}
void fibo_gen(int initial_value,int final_value,int count)
{
int temp;
if (count>0)
{
System.out.print(initial_value+" , ");
temp=initial_value+final_value;
initial_value=final_value;
final_value=temp;
count=count-1;
fibo_gen(initial_value,final_value,count);
}
else
System.out.println(initial_value);
}
}
C:\>javac FibonSeries.java
C:\>java FibonSeries
Fibonacci series using Recursion :
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55
Conclusion
Recursion is a great art, enabling programs for which it is easy to verify correctness without sacrificing performance, but it requires the programmer to look at programming in a new light.
Imperative programming is often a more natural and intuitive starting place for new programmers which is why most programming introductions focus on imperative languages and methods.
But as programs become more complex, recursive programming gives the programmer a better way of organizing code in a way that is both maintainable and logically consistent.
Recent Comments