[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

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.

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); } }

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.