5. Function (2)–Function recursion

Recursion is recursion and regression, regression function value, and recursion function process

2. Restrictions on recursion

• There are restrictions on recursion. If this condition is met, the recursion will no longer proceed.
• After each recursive call, the recursion condition will gradually approach.

Eg: Find the factorial of n!

int fact(int n){<!-- -->
int result = 0;
if (n == 0) {<!-- -->
result = 1;}
else result = n * fact(n - 1);
return result;
}
int main(){<!-- -->
int n = 0;
scanf("%d", & amp;n);
int result = fact(n);

printf("%d ", result);
return 0;}

There are a few points I want to emphasize here:

1. It is best to define a function with only one return value. Although having multiple returns is more concise, it is not conducive to the logic and error checking capabilities of the code.
2. What’s the idea?

The factorial of each number is the product of the factorial of the previous number and itself!

n*fact（n-1） This is what it does

3. Pay attention to understanding the role of regression and recursion!

Let’s analyze the process of recursion and regression:

That is to say, when thinking, we have to think in reverse, that is, to imagine the result of the recursion to the end. Then regression is the process of reversely implementing the recursion we constructed.

Let’s look at a slightly more difficult example: outputting the input numbers sequentially:

void Print(int n)
{<!-- -->
if (n > 9)
{<!-- -->
Print(n/10);
}
printf("%d",n );
}
int main()
{<!-- -->
int n = 0;
scanf("%d", & amp;n);
Print(n);}

These two examples are enough to illustrate recursive thinking! Especially in the second example, we use a better algorithm to split the problem into:

The process of printing the remainder and returning the original number by dividing it by 10!

Detailed explanation: The remainder of any number to 10 is its single-digit value. For example, if I input 1234, 4321 will be printed out in the forward direction, and recursive regression is used to run in reverse, so the 1234 I input will print out 1234. That is:

If you still don’t understand, quickly use the flow chart to analyze it!

3. Recursion and iteration

3.1Some things you should know about recursion

We already know that recursion only uses a small amount of code to complete a large number of operations, which is naturally the advantage of recursion.

But like many techniques, it can be easily misused! We need to know that derivation ≠ recursion!

Please allow me to repeat: in C language, every time a function is called, a block of memory space needs to be allocated in the stack area for this function call to save the values of various local variables during the function call. This space is called It is the runtime stack or function stack frame.

Why is it so important?

This is because if the function does not return, the stack frame space corresponding to the function will be occupied directly. Therefore, if there is a recursive call in the function call, each recursive function call will open up the stack frame space belonging to the function until The function recursion no longer continues and starts to return, and then the stack frame space is released layer by layer.

Therefore, if you use function recursion to complete the code, if the recursion level is too deep, too much stack frame space will be wasted, and it may also cause stack overflow problems.

3.2Iteration

If you don’t want to use recursion, you have to think of other ways. Iteration (usually loop) helps us replace recursion.

Please allow me to give another example of calculating factorial (because it is simple and easy to understand):

int Fact(int n)
{<!-- --> int i = 0;
  int ret = i;
for(i=1;i<=n;i + + ){<!-- -->
ret = ret * i; return ret;
}}

I would like to say that many problems solved through recursion can be solved through iteration. Please use recursion to solve the problem again when you encounter complex problems that are difficult to implement/explain using iteration.

3.3Fibonacci Sequence Problem

3.3.1Fibonacci Sequence

Maybe you have already been tortured by various OJs with this kind of problem, but I still advise you to read on patiently.

Use recursive thinking to describe the Fibonacci sequence:

 Result: Fibs =

(

n

< = 2 , 1 n >

2

,

F

i

b

(

n

?

1

)

+

F

i

b

(

n

?

2

)

)

\binom{ n< = 2,1 } {n>2,Fib(n-1) + Fib(n-2)}

(n>2,Fib(n?1) + Fib(n?2)n<=2,1?)

But the problem is that once n is relatively large, this will occupy a lot of memory space. For example, n=40 will occupy a huge amount of memory!

It takes so many regressions to calculate this result! It can be seen that function recursion consumes resources and has extremely low efficiency!

So if you encounter this kind of problem, just write iterations honestly!

This calculation is fast and does not take up resources!

3.3.2Advanced Fibonacci Sequence

Let’s first summarize the choice between recursion and looping:

1. If writing code using recursion is extremely easy and less expensive, then recurse
2. If there are clear drawbacks to using recursion, then it should be used!

Let’s take a look atFibonacci-like sequence problems:

• We need to review some high school mathematics knowledge first

  There are 6 steps. Xiao Ming can walk one step/two steps at a time. How many ways can he walk up 6 steps? The answer is 13!

  

  It was obvious that there was only one way for us to get to the first step. At the same time, we have two ways to walk up the second step: we can go up from the first step, or we can go up two steps, so there are two ways to go up the second step. What about the third step? We can go up from the first step or the second step. Please note:< strong> If you go up the first step, then you must include all the ways to get to the first step. Going up the second step includes the steps on how to get up the second step, so there are 1 + 2 = 3 ways to get up the third step! By analogy, we know that the number of moves on each step is equal to the sum of the number of moves on the previous two steps.

  Code:

  int main()
  {<!-- -->
  int ladder = 4;
  int a_1 = 1;
  int a_2 = 2;
  int a_3 = 0;
  while (ladder) {<!-- -->
  a_3 = a_1 + a_2;
  a_1 = a_2; a_2 = a_3;
  ladder--;
  }
  printf("%d", a_3);
  return 0;
  }int main()
  {<!-- -->
  int ladder = 4;
  int a_1 = 1;
  int a_2 = 2;
  int a_3 = 0;
  while (ladder) {<!-- -->
  a_3 = a_1 + a_2;
  a_1 = a_2; a_2 = a_3;
  ladder--;}
  printf("%d", a_3);
  return 0;}
  

  //Use recursion:
  int f_1(int n_0)
  {<!-- -->
  if (n_0 == 1) return 1;
  else if (n_0 == 2) return 2;
  else return f_1(n_0 - 1) + f_1(n_0 - 2);
  }
  int main()
  
  {<!-- -->
  int n_0 = 6;
  int m =f_1(n_0);
  printf("%d", m);
  return 0;
  }
  

• 1. Frog jumping problem:

  Once upon a time, there was a frog who wanted to jump up the steps to wait for the peak. If the frog could jump up one step at a time, he could also jump up two steps…(n-1) level, n level. Then how many ways can the frog jump up the nth step? (The premise is that there will be an n-level jump for n steps)

  This is indeed difficult, but don’t worry, let’s analyze the problem step by step:

  1. We get the information from the question: the frog can jump any step at a time but cannot jump back. **That is to say, the frog’s goal is on any step, and it can reach its destination step from any step.
  2. From this we get the first equation:f(n)=f(n-1) + f(n-2) + f(n-3)……… + f(1).
  3. Any step meets the requirement, thenf(n-1)=f(n-2) + …….f(1). From this we get the second equation of f(n) = 2f(n-1)
  4. So our recursive idea is to find the value of the next step number corresponding to each step, combined with the Fibonacci principle.

  int f_2(int n)
  {<!-- -->
  int cnt = 1;
  if (n == 1) return cnt;
  else cnt = 2*f_2(n-1);
  return cnt;
  }
  int main()
  {<!-- -->
  int n = 0; //n is the number of steps!
  scanf("%d", & amp;n);
  int count = f_2(n);
  printf("%d", count);
  return 0;
  }
  

• 2. Tower of Hanoi problem:

  As shown in the figure below, there are three pillars A, B, and C from left to right. On pillar A, there are n discs stacked from small to large. Now it is required to move the discs on pillar A to pillar C. During this period, only One principle: you can only move one plate at a time and the big plate cannot be on top of the small plate. Find the steps of moving and the number of moves.
  

  Suppose there are only 3 plates, how should we move them? We first move A to C, then move A to B, then move C to B, move A to C, then move B to A, B to C, and finally move A to C. as the picture shows:

  

  That is to say, we have to do:

  1. Step n-1, move B to C (with the help of a)
  2. Step n-2, move A to C, (with the help of b)

  No matter how many plates there are, the final steps are these two. The reason is to meet the conditions of the question.

  void move(char a, char b)
  {<!-- -->
  printf("%c->%c", a, b);
  printf("\
  ");
  }
  
  void hanoi(int n, char a, char b, char c)
  {<!-- -->
  if (n == 1) {<!-- -->
  move(a, c);
  }
  else if (n == 2) {<!-- -->
  move(a, b);
  move(a, c);
  move(b, c);
  }
  else
  {<!-- -->
  hanoi(n-1,a,c,b);
  move(a, c);
  hanoi(n - 1, b, a, c);
  }
  }
  
  int main()
  {<!-- -->
  int n = 0;
  scanf("%d", & amp;n);
  {<!-- -->
  hanoi(n, 'A', 'B', 'C');
  }
  return 0;
  }
  

4. A deeper understanding of function recursion

int sum = 0;
int DigitSum(int n)
{<!-- -->
if (n > 9) {<!-- -->
DigitSum(n/10);
}
int num = n % 10;
sum = sum + num;
return sum;
}

int main()
{<!-- -->
int n = 0;
scanf("%d", & amp;n);
printf("%d",DigitSum(n));
return 0;
}

This is a recursive method to find the sum of the digits of a number.

I want to emphasize that in recursion, what I return is sum

Instead of writing it like this:

int DigitSum(int n)
{<!-- -->
    if (n <= 9) {<!-- -->
        return n;
    }
    int num = n % 10;
    int remainingSum = DigitSum(n / 10);
    return remainingSum + num; }

Note that the value returned in the recursion will enter the next recursive function in the regression without stopping or going somewhere else!

What are the advantages and disadvantages of these two ways of writing?

1. How to use global variables (original code):
   • Simpler since no extra parameters need to be passed and returned.
   • It’s probably easier to understand because on each recursive call the numeric sum is accumulated directly in the global variable sum.
2. Recursive pass and return (another code):
   • It is more in line with the functional programming way of thinking because it avoids the use of global variables.
   • Probably easier to maintain since there is no global state and each recursive call returns partial results.

Generally, if the code does not need to maintain global state, it is a good practice to avoid using global variables. Therefore, the pass and return approach is more maintainable and readable. But if your code is a small, simple tool, it might be more convenient to use global variables.

Ultimately, which approach you choose depends on your specific needs and the context of your code. If there is no problem using global variables throughout the program, and the code is clear enough, then the original code is good enough. If you prefer to follow functional programming principles, or if the context of your code is more complex, the pass-and-return approach may be more appropriate.