Overview
- what is a recursion ?
- Recursion Tree / Tracing code
- How to approach recursive solution
- Few Examples
What Is A Recursion ?
- Function calling itself is called recursion
- A recursive method solves aproblem by
calling a copy of itself to work on asmaller problem - It is important to ensure that
the recursion terminates
void f1()
{
s.o.p("Hello");
f1();
s.o.p("Bye");
}
void f2()
{
s.o.p("A");
}
- Each time the function call itself with a slightly simpler version of the original problem
- Recursive code is generally shorter and easier to write than iterative code
- Solution to some problems are easier to formulate recursively
Recursion Tree
public static void main(String[]srg)
{
Example obj=new example();
int k;
k=obj.f1(3);
s.o.p(k);
}
public int f1(int n)
{
int s;
if(n==1)
return(1);
s=n+f1(n-1);
return(s);
}
- f1(3)=3+2+1
- f1(5)=5+4+3+2+1
How To Approach A Recursive Problem?
- Write a recursive function to calculate sum of first n natural numbers
int sum(int n)
{
if(n==1)
return(1);
return n+sum(n-1);
}
- Write a recursive function to print first n natural number
void part n(int n)
{
if(n>0){
printn(n-1);
s.o.p(n);
}
}
