DOWNLOAD MATERI STRUKTUR DATA (Lecture (SD-04 Recursion & Binary Tree)

LECTURE (SD-04) RECURSION & BINARY TREE

Recursion Algorithm

Almost repetition can be achieved by writing loops, such as for loops and while loops. 

Another way to achieve repetition is through recursion .

Recursion algorithm provides an elegant and powerful alternative for performing repetitive, If :

1. a method is called with a more complex problem, 
2. the method divides the problem into two or more conceptual pieces: a piece that the method knows how to do and a slightly smaller version of the original problem. 

Recursion Vs Iteration

For recursion to terminate, each time the recursion method calls itself simple version of the original problem, the sequence of smaller and smaller problems must converge on the base case. 

When the method recognizes the base case, the result is returned to the previous method call and a sequence of returns ensures all the way up the line until the original call of the method eventually returns the final result. 

Recursion Vs Iteration

1. Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated method calls. 
2. Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized

Recursion Vs Iteration

1. Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case. 
2. Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls. This can be expensive in both processor time and memory space.

Recursion Vs Iteration

Solve factorial problem

Recursion Vs Iteration

Example, solve factorial problem

Use Iteration methode:

public int iteration(int n){

        int result=1;

        if(n==0){

            return result;

        }

        else{

            for(int i=n; i>0; --i){

                result *= i;

            }

        }

        return result;

    }

Recursion Vs Iteration

Example, solve factorial problem

Use Recursion methode:

Recursion Vs Iteration

Example, solve factorial problem

Use Recursion methode:

public int recursion(int n){

        if(n==0){

            return 1;

        }

        else

            return n * recursion(n-1);

    }

Benchmark Recursion Vs Iteration

public static void main(String[] args){

        Factorial f = new Factorial();

        //recursion

        long now2 = System.nanoTime();

        System.out.println(f.recursion(5)); 

        long after2 =  System.nanoTime();

        long tr = after2-now2;

        //iteration

        long now1 = System.nanoTime();

        System.out.println(f.iteration(5)); 

        long after1 =  System.nanoTime();

        long ti = after1-now1;

        //comparation

        System.out.println("time for iterative " +ti + " \n vs time for recursion " + tr);

    } 

Output,

run:

120

120

time for iterative 107785 

 vs time for recursion 367703

BUILD SUCCESSFUL (total time: 0 seconds)

Benchmark Recursion Vs Iteration

In simple algorithm like factorial case, iteration is faster then recursion for time execution.

Selengkapnya silahkan Download Disini

Materi ini di ajarkan di Universitas Trunojoyo Madura (UTM) Jurusan Teknik Informatika. Semoga bermanfaat ^_^

Kritik dan Saran layangkan ke Facebook dan Email: Hasan.kawaguchi24@gmail.com