C language – recursion and iteration

write in front
Hello everyone, I am Aileen. I hope it can be helpful to you after reading this. Please correct me if I am wrong! Learn and communicate together.
This article was originally published by Aileen_0v0 on CSDN If you need to reprint it, please notify us
Personal homepage: Aileen_0v0-CSDN blog
Welcome everyone → Like + Collection + Leave a message?
Column series: Aileen_0v0’s C language learning column series – CSDN blog
My motto: “If there is no Rome, then create Rome yourself~”

Table of Contents

recursive concept

recursive thinking

Recursive constraints

example

1. Find the factorial

2. Print in order

Recursion and iteration

example

1. Find the nth Fibonacci number

?Edit Use recursion to find

Use iteration to find

Summary

Preview

1. Tower of Hanoi problem

2. The frog jumping problem

---

Summary of this section

Recursive concept

Recursion: the function calls itself

Console running results:

Recursive Thought

Convert a large problem into a sub-problem that is similar to the original problem but smaller in scale; until the sub-problem can no longer be split, the recursion ends. — Big things are reduced to small ones

Recursive means recursion and recursion means regression

Recursive constraints

example

1. Find factorial

Stack overflow is not considered, so n cannot be too large. The factorial of n is the cumulative multiplication of 1-n numbers.

int Fact(int n)
{
if (n <= 0)
return 1;
else
return n * Fact(n - 1);
}

int main()
{
int n = 0;
scanf("%d", & amp;n);
int ret = Fact(n);
printf("%d\
", ret);
return 0;
}

Illustration of the process of finding factorial (take 3 as an example). Red represents the regressive process and green represents the regression process.

2. Print in order

1.Print(
1234
)

2.==>Print(
123
) +
printf
(
4
)

3.==>Print(
12
) +
printf
(
3
)

4.==>Print(
1
) +
printf
(
2
)

5.==>
printf
(
1
)

Drawing deduction:

//Print in order
void Print(int n)
{
if (n > 9)
Print(n/10);
printf("%d ", n % 10);
}


int main()
{
int n = 0;
scanf("%d", & amp;n); //1234
Print(n);
return 0;

}

Run results:

In C language, if both the dividend and the divisor are integers, the result will be truncated to an integer without a decimal part when the division sign / is used. If at least one of the dividend and divisor is a floating point number, the result will retain the fractional part when operating with the division sign /. For example:

int a = 5, b = 2;
float c = 5.0, d = 2.0;

int result1 = a / b; // The result is 2
float result2 = a / b; // The result is 2.0
float result3 = c / d; // The result is 2.5

In the first example, because both the dividend and the divisor are integers, the result is truncated to the integer 2. In the second example, although an integer variable is used, the result is converted to a floating point number of 2.0 because the operation result is stored in a floating point variable. In the third example, the dividend and divisor are both floating point numbers, so the result retains the decimal part and is a floating point number of 2.5.

Recursion and Iteration

Although recursion is very useful, stack overflow problems may occur if the recursion depth is too deep.

This is an example of just printing 1234. We use the stack area in the function memory to observe how it prints.After all functions are executed, we will find that there will be Create a space for each executed function. These spaces will not be released one by one until the function is executed.

If the printed number is very large, for example, n = 10000 and the stack memory is not that large, it will result in not enough space in the stack area for the function to open the stack frame >, the phenomenon of stack over flow will occur.

void test(int n)
{
if (n <= 10000)
{
printf("%d\
", n);
test(n + 1);
}
}
int main()
{
test(1);
return 0;
}

The recursion level is too deep and stack overflow occurs

Iteration: represents something that is done repeatedly, and a loop is a kind of iteration

We can solve the factorial problem through iteration (loop)

int main()
{
int n = 0;
scanf("%d", & amp;n);
int i = 0;
int ret = 1;
for (i = 1; i <= n; i + + )
{
ret *= i;
}
printf("%d\
", ret);
return 0;
}

operation result:

Example

1. Find the nth Fibonacci number

Fibonacci Sequence: 1 1 2 3 5 8 13 21 34 55

Use recursion

//Find the nth Fibonacci number
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}

int main()
{
int n = 0;
scanf("%d", & amp;n);
int ret = Fib(n);
printf("%d\
", ret);
return 0;
}

operation result:

//Find the nth Fibonacci number
int count = 0;
int Fib(int n)
{
if(n==3)
count + + ;
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}

int main()
{
int n = 0;
scanf("%d", & amp;n);
int ret = Fib(n);
printf("%d\
", ret);
printf("count = %d\
", count);
return 0;
}

Find using iteration

int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}

int main()
{
int n = 0;
scanf("%d", & amp;n);
int ret = Fib(n);
printf("%d\
", ret);
//printf("count = %d\
", count);
return 0;
}

operation result:

Summary

1. If you use the recursive method to write code for a problem, it is very convenient and simple

The code written is without obvious flaws. In this case, recursion can be used.

2. If the code written using recursion is obviously flawed

For example: Stack overflow, low efficiency, etc.

At this time, you mustconsider other methods, such as: iteration

Preview

1. Tower of Hanoi problem

According to legend, in ancient Indian temples, there was a game called the Tower of Hanoi. The game is on a copper plate device with three poles (numbered A, B, C). On pole A, 64 gold disks are placed in order from bottom to top and from large to small. The goal of the game is to move all the gold plates on pole A to pole C and keep them stacked in the original order. Operating rules: Only one plate can be moved at a time, and during the movement, the large plate is always on the bottom and the small plate is on the top of the three rods. During the operation, the plate can be placed on any of the rods A, B, and C.

2. The frog jumping up the steps problem

There is a frog. It can jump one step at a time, or it can jump 2 steps. If there are n steps, how many ways can this frog jump up to n steps?

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57137 people are learning the system