cool hit counter [J2SE Fast Forward] - Recursive Algorithms_Intefrankly

[J2SE Fast Forward] - Recursive Algorithms


Copyright: This is an original post by the blogger and may not be reproduced without the blogger's permission. https://blog.csdn.net/huyuyang6688/article/details/42149477

recursive algorithm

Recursion, as defined by Baidu's encyclopedia, is a programming technique in which a program calls itself. To be clear, a function or procedure will call itself when executed.

Let's start with an example of "finding the factorial of a number".

public class Test {
	public static void main(String[] args) {
		System.out.println(Method(3));
	}
	public static int Method(int n){
		if(n==1)
			return 1;
		else
			return n*Method(n-1);				
	}	
}

As can be seen from the program, the Method() function serves to calculate the factorial of the parameter n. When the value of n is 1, the result is returned directly as 1; otherwise, the statement under else is executed and the Method() function is called again, and the period execution process is as follows.

propern=3 time,executeelse underreturn 3*Method(2),Method(2) i.e. with2 The function is re-called for the real parameterMethod() themselves; for the same reason,n=2 time,executeelse underreturn2*Method(1);n=1 time, Direct return1。

When you get to it, you will find that recursion can transform a large, complex problem layer by layer into a smaller scale problem similar to the original problem to solve, requiring only a small amount of program code to describe the many iterations of computation required to solve the problem, greatly reducing the amount of code in the program.

Recursion has the following characteristics.

1、 Recursive implementation time, is to transform a problem into a similar smaller-scale problem, And this new problem is solved in the same way as the original problem, It just deals with different objects, The simplest solution is derived by multiple recursions, Then return up the call layer by layer, final solution。;

2, recursion to have an end condition, used to terminate the loop call, that is, when this condition is met, no more recursion, otherwise keep calling itself, know to meet this bar. (The if(n==1) in the above example is the end condition)

3, although recursion in a certain degree to make the code to achieve reuse, but deep recursion will involve frequent stack in and out and allocation of memory space, so the operating efficiency is relatively low, when the problem size is large, is not recommended to use.

4, in the recursive process, each call in the parameters, method return point, local variables are stored in the stack, if when the problem size is very large, easy to cause a stack overflow.

Examples of recursive implementations

To refresh your memory, here are a few small examples that can be implemented with recursion

1. Find the sum of 1+2+3+......+100

public class Sum {
	public static void main(String[] args) {
		System.out.println(sum(100));
	}
	public static int sum(int num){
        if(num <= 0){
         	return 0;                 //Loop ends when num=0           
        }else{
         	return num + sum(num-1);  // Calling recursive methods 
        }     
 }    

2. Convert decimal numbers to binary numbers

public class DecimalToBinary {
	public static void main(String[] args) {
		DecimalToBinary(118);
	}
	public static void DecimalToBinary(int num){
        <span style="white-space:pre">	</span>if(num ==0){                    // propernum=0 time, End of the cycle
               <span style="white-space:pre">	</span>       return;
       <span style="white-space:pre">	</span>        }else{
                      DecimalToBinary(num/2);  // Calling recursive methods
                      System.out.print (num%2);
       <span style="white-space:pre">	</span>        }
        }  
}

3. Calculate the Fibonacci series

public class Fibonacci{
	public static void main(String[] args) {
		System.out.println(fib(4));
	}
   static int fib(int n)  
	{  
	   if(n==0||n==1)  
	       return n;  	    
	   else  
	       return fib(n-1)+fib(n-2);  
	}  
}

The difference between recursion and iteration

Some beginners may sometimes confuse the two algorithms, recursion, which is an algorithm in which a function (or procedure) seeks an end result by continually making calls to itself, and iteration, which can be thought of as a loop.

The example at the beginning of the article can be implemented using iteration as follows.

public class Test {
	public static void main(String[] args) {
		System.out.println(Method(3));
	}
	public static int Method(int n){
		int product=1;
		for(int i=n;i>0;i--){
			product=product*i;
		}
		return product;		
	}
}

From the code, we can find that iteration is simply a loop that loops from i=n all the way to i=1, and finally just returns the final solution product directly; while recursion transforms the much-needed problem into a similar problem of smaller size, arrives at the simplest solution through multiple recursions, and then returns the call upwards layer by layer to get the final solution. Recursion here is like the same reason we climb a mountain, one step at a time, and then eventually descend one step at a time once we reach the top.


Recommended>>
1、PythonTeaching from the ground up Day 3
2、Watch out for the pigs on your cell phone
3、中国科学家力推全球地球大数据研究
4、Decision Science Court uses multiple rounds of decision making to personalize decisions
5、How to implement a distributed application configuration center using Zookeeper

    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号