Shulou(Shulou.com)06/02 Report--

This article mainly introduces "the recursive usage in C language". In the daily operation, I believe that many people have doubts about the recursive usage in C language. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about the recursive usage in C language! Next, please follow the editor to study!

What is recursion?

When it comes to recursion without stack, I think it is a bit inappropriate. The characteristic of recursion is that it keeps calling the same function. If this function does not have a recursive boundary, it is an endless loop, so when discussing recursion, we must discuss the boundary of recursion, that is, to limit how many times this recursion can be called.

Let's look at an example.

# include "stdio.h"

Int digui (unsigned long count)

{

If (count > 0) {

Count--

Printf ("% d\ n", count)

Digui (count)

}

Return 1

}

Int main ()

{

Digui (10)

Return (100)

}

The qualified interpretation of this recursive function is

If (count > 0) {

So the order of his calls can be illustrated by this diagram.

This process is called passing, that is, the process of pressing the stack. since there is a process of pressing the stack, then there is a process of getting out of the stack, and the process of getting out of the stack is

If (count > 0) {

After the judgment is not successful, it will be out of the stack. As shown in the following figure

How many recursions can be performed?

As we mentioned above, since the stack is recursively used, then the stack size of the system must have a limit, and it is impossible for the system to assign you an unlimited stack size. I read some articles saying that the stack size is 64K.

Again with the above example, I set the incoming data to be very large for execution.

# include "stdio.h"

Int tigui (unsigned long count)

{

If (count > 0) {

Count--

Printf ("% d\ n", count)

Tigui (count)

}

Return 1

}

Int main ()

{

Tigui (900000)

Return (100)

}

Execution result

So there must be a limit to the number of recursions.

Recursive factorial

Using recursive factorial is a classic method. Let's take a look at the code.

# include

Int fact (unsigned long n); / / declare factorial fact function

Int main () {

Unsigned long x

Scanf (& d, & x)

X = fact (x); / / call function to return int value

Printf ("% ld\ n", x)

Return (0)

}

Int fact (unsigned long n) {/ / define factorial function

If (naughter1) return 1 / input parameter is 1, return 1 directly

Else return n*fact (nmur1); / / Recursive algorithm

}

Execution result

Just looking at the code, I think it's still a bit of a mouthful. Let's look at a picture to see his call, assuming we're asking for a factorial of 5.

Recursion and Hanoi Tower

Hanoi Tower: the problem with Hanoi Tower (also known as Hanoi Tower) stems from an ancient Indian legend of educational toys. When Brahma created the world, he made three diamond pillars, on which 64 gold discs were stacked from bottom to top. Brahma ordered the Brahmin to rearrange the disc on another pillar in order of size from below. It is also stipulated that the disk cannot be enlarged on the small disc and can only be moved one disk at a time between the three columns.

If it is such a Hanoi Tower, I think everyone should think it is very simple, it only takes three steps to complete the movement.

1. Put the small disk on the third column 2, put the middle disc on the second column 3, put the small disk on the second column 4, put the large disk on the third column 5, put the small disk on the first column 6, put the middle disc on the third pillar 7, put the small disc on the third column

As shown in the figure

The analysis above is the method of subdivision, and the core idea of mobile is divided into three steps.

1. Move the nmur1 disc on the first column to the second column. 2. Move the nth disc of the first column to the third column. 3. Move 1 disc of the second column to the third column.

So recursion appears.

1. Move the nmur1 disc on the first column to the "recursive implementation" on the second column. 2. Move the nth disc of the first column to the third column. 3. Move one disc of the second column to the third column "recursive implementation".

C language code implementation

# include

# include

Void Hanoi (int n, char a mai char bmae char c)

Void Move (int n, char a, char b)

Int count

Int main ()

{

Int nasty 8

Printf ("number of floors of the Tower of Hanoi:\ n")

Scanf ("d", & n)

Hanoi (n,'A','B','C')

Printf ("Exiting main...\ n")

Return 0

}

Void Hanoi (int n, char a, char b, char c)

{

If (n = = 1)

{

Move (n, a, c)

}

Else

{

Hanoi (nmur1, a, c, b); / * put nmur1 from pillar a to pillar b * /

Move (n, a, c); / * move n from a to c * /

Hanoi (n-1, b, a, c); / * move n-1 from b to c through the auxiliary effect of a * /

}

}

Void Move (int n, char a, char b)

{

Count++

Printf ("% d move Move% d: move from% c position to% c!\ n", count,n,a,b)

}

Output as shown in the figure

Enhanced version modification

Strengthen the software writing, take a good look at the code, write a little too fast, did not think about it, and then improve it.

# include

/ * flexible array * /

Typedef struct _ soft_array {

Int len

Int array []

} soft_array

/ * Hanoi Tower structure * /

Typedef struct _ hannuo {

Soft_array * p_data

Char name

} hannuo

Hannuo * han_a = NULL

Hannuo * han_b = NULL

Hannuo * han_c = NULL

Void hannoiii (int n recorder hannuo * a recital hannuo * b recorder hannuo * c)

Void moveiii (int njen hannuo * a dint hannuo * c)

Int total

Void printf_han_data (hannuo * han)

{

Int I = 0

Printf ("% c:", han- > name)

/ * output data from Tower Hanoi * /

For (I = 0 / 0 / ipiproomdata-> len;i++)

{

Printf ("% d -", han- > pairdata-> array [I])

}

Printf ("\ n")

}

Int main ()

{

Int I = 0

Int n = 0

Scanf ("d", & n)

Total = n

/ * define three Hanoi nodes * /

Han_a = (hannuo *) malloc (sizeof (hannuo))

Han_a- > name ='A'

Han_a- > p_data = (soft_array*) malloc (sizeof (soft_array) + sizeof (int) * n)

Han_a- > pendant data-> len = n

/ * the data was originally on the first pillar * /

For (I = 0 / array _ data-> iFig _ 1

}

Printf_han_data (han_a)

/ * initialize the second column * /

Han_b = (hannuo *) malloc (sizeof (hannuo))

Han_b- > name ='B'

Han_b- > p_data = (soft_array*) malloc (sizeof (soft_array) + sizeof (int) * n)

Memset (han_b- > pairdataPrecedence Sizeof (soft_array) + sizeof (int) * n)

Han_b- > pendant data-> len = n

Printf_han_data (han_b)

/ * initialize the third column * /

Han_c = (hannuo *) malloc (sizeof (hannuo))

Han_c- > name ='C'

Han_c- > p_data = (soft_array*) malloc (sizeof (soft_array) + sizeof (int) * n)

Memset (han_c- > pairdataPrecedence Sizeof (soft_array) + sizeof (int) * n)

Han_c- > pendant data-> len = n

Printf_han_data (han_c)

Printf ("-\ n")

Hannoiii (n Hanqia, Hanqia, Hanqbh, Hanqc)

Printf ("\ n")

Return 0

}

Void hannoiii (int n recorder hannuo * a recital hannuo * b recorder hannuo * c)

{

If (n = = 1)

{

A-> pairdata-> array [0] = 0

C-> proomdata-> array [0] = 1

Printf_han_data (han_a)

Printf_han_data (han_b)

Printf_han_data (han_c)

Printf ("-\ n")

}

Else

{

Hannoiii (nmur1, a, c, b); / * put nmur1 from pillar a to pillar b * /

Moveiii (n, a, c); / * move n from a to c * /

Printf_han_data (han_a)

Printf_han_data (han_b)

Printf_han_data (han_c)

Printf ("-\ n")

Hannoiii (n-1, b, a, c); / * move n-1 from b to c through the auxiliary effect of a * /

}

}

Void moveiii (int njen hannuo * a dint hannuo * c)

{

Int I = 0

Int tmp = a-> pairdata-> Array [n-1]

A-> pairdata-> array [n-1] = 0

# if 1

C-> pairdata-> Array [n-1] = tmp

# else

For (I = 0 position I)

< total;i++) { if(c->

Pairdata-> array [I] = = 0) {

C-> pairdata-> array [I] = tmp

Break

}

}

# endif

At this point, the study of "Recursive usage in C language" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.