Java Understand the idea of recursive programming with method stack frame

Introduction to recursion

In computer programming, the term recursive describes a function or method that repeatedly calculates a smaller part of itself to arrive at the final result. It is similar to iteration, but instead of repeating a set of operations, a recursive function accomplishes repetition by referring to itself in its own definition. While the concept of recursive programming can be difficult to grasp initially, mastering it can be very useful. Recursion is one of the fundamental tools of computer science.

In computer programming , Recursion describes a function or method that repeatedly computes a smaller part of itself , To get the final result . It’s kind of like iteration , But not a series of common operations , It is to call itself repeatedly to complete in its own definition . The concept of recursion is really difficult to understand , But understanding is extremely useful . Recursion is one of the tools of computer science .

The above is a more academic statement , About recursion , In short —— function （ Or some languages call methods ） The body calls itself , So as to get the final result .

Recursion considerations

• Be sure to guarantee the condition of recursive termination , Otherwise, it will fall into the nightmare of infinite calls
• Every time a recursive , It should solve the problem of smaller subsets

Factorial —— Introduction to recursion

Factorial ： It’s the best case of recursion .

0 The factorial =1; —– because 1!=1, according to 1!=1*0!, therefore 0!=1 instead of 0.

1 The factorial =1;

2 The factorial =2*1!=2;

3 The factorial =3*2!=6;

4 The factorial =4*3!=24;

We find a non negative factorial = Its value *( Its value -1)!

In programming , This is how to find the order of a given number ：

private int factorial(int i){

if( i <= 1 ){

return 1;
}else{

return i * factorial(i-1);
}
}

The results verify that … No problem ！

Recursion and method stack

Take a look back. ：JMM Memory model .

For the above code ：

private int factorial(int i){

if( i <= 1 ){

return 1;
}else{

return i * factorial(i-1);
}
}

combination JMM Let’s analyze the model , Each method call has its own stack frame ; So every time it’s called

① Save the local variables of the current stack frame

② operation , To continue to call smaller than it 1 The stack frame

③ Carry on ①-③, Know to find the last one —— Recursive termination condition return 1

④ Method step by step , Go back to the stack frame of the previous layer … Until the first stack frame , Get the results , Out of the stack .

This process requires a lot of stack frames , We know that stack frames need a certain amount of memory , So there’s a lot of space loss ;

Tail recursive optimization

Tail recursion —— When called recursively, the last statement is the function itself , And there’s no other expression ;

For tail recursion , Modern compilers will optimize it , Reuse stack frame .

rewrite , Use tail recursion , Reuse stack frame ：

private int factorial2(int i, int result){

if( i <= 1 ){

return result;
}else{

return factorial2(i-1, i*result);
}
}

The final execution statement contains only the method itself , Then stack frame can be reused , Just one stack frame .

Hanoi tower realizes

After understanding the idea of recursion , Let’s take a look at a case in the data structure class ： Hanoi .

For starters , This case is a headache … Seems to be in a state of no solution …

• At first, the disk was all in the same place as the superimposed arhat A, There are free pillars B、C;
• The final requirement is to put it all in C disc ;
• The disk can be moved in any column ;
• Only one disk can be moved at a time ;
• During movement , We need to make sure that all the columns are on the bottom floor , The top is a small dish ;

analysis

If there is a solution to this problem , So it should be recursion 、 Loop to achieve ;

recursive ？ How to recurse ？

How to split task subsets ？

Realization

hypothesis A There is 2 Disc —— Move to as is C, You need to go through the following steps ;

A Move to B

A Move to C

B Move to C

alike N individual , You can put the following N-1 As a whole , The top one , Make two together ; Do as above ;

This is constant subdivision , Each piece is a repetitive action , It can be implemented recursively .

In essence, it’s a stack 、 The process of getting out of the stack

// take n A disk from a Through b Move to c On 
public void hanoid(int n, char a, char b, char c) {

if (n <= 0) {

return;
}
// The above n-1 A disk moves to B
hanoid(n-1, a, c, b);
// At this time will be A The biggest disc at the bottom moved to C
move(a, c);
// then B Upper n-1 A disk passes through A Move to C On 
hanoid(n-1, b, a, c);
}
public void move(char a, char b) {

printf("%c->%c\n", a, b);
}