What is recursion in c language? Classic recursive function example sharing

What is recursion in c language? The following article will help you understand recursion in C language through classic recursive function examples. I hope it will be helpful to you!

Recursion is a method of calling itself directly or indirectly in its definition or description; a recursive function is a method of directly or indirectly calling itself Calling its own function means calling its own process.

Students who are new to recursion may find it difficult to understand recursion. There may be many difficult points to understand, such as:

• Why can functions be called within themselves? What about yourself?

• Since you can call yourself, there must be many layers nested in each other during the recursive operation. When will they no longer be nested?

• During the recursive operation, parameters will be passed between multiple layers nested with each other. Will the multiple layers affect each other?

Two elements of recursion

• Recursion boundary

• The logic of recursion - recursion" formula "

The recursive process must have parameter changes, and the parameter changes are related to the recursion boundary.

In more difficult questions, these two It is not easy to get it directly.

Regarding the various problems of recursion, students who understand may be able to explain it clearly in one sentence, but students who do not understand will not be able to understand it no matter how much they say.

The following is passed A few simple examples to [experience] recursion, first understand recursion from a [perceptual] perspective.

1.Fibonacci number

We arrive at the recursion of Fibonacci number The formula is: F(0)=F(1)=1,F(n)=F(n-1) F(n-2) n>=2;

This obviously gives the recursion The value of F(n) when boundary n=0 or 1, and the recursive logic F(n)=F(n-1) F(n-2), that is, the recursive formula. So this recursive function is not difficult to write

#includeusing namespace std;
int F(int n)//函数返回一个数对应的Fibonacci数{ if(n0 || n1)//递归边界
return 1; return F(n-1) + F(n-2);//递归公式}
int main(){ //测试
int n; while(cin >> n) cout << F(n) << endl;
return 0;
}

2. The recursive formula of factorial: n*F(n-1)

The code is as follows:

#includeusing namespace std;
int F(int n){ if(n==0)//递归边界
return 1;
return n*F(n-1);//递归公式}
int main(){ int n; cin >> n; cout << F(n) << endl;
return 0;
}

3. Array summation

Given an array a[]:a[0],a[1],...,a[n-1], how to sum it recursively?

There are still two questions: recursion boundary and recursion formula.

What is the recursion boundary? It is not easy to think of it at the moment, but we think of summation. What is the process of summing multiple numbers? What is the process of manually summing x, y, z, w? The steps are as follows:

x y=a, the task becomes a, z, w sum

a z=b, the task becomes b, w sum

b w=c Get the answer

Think about it, [Get the answer] Why can you get the answer in this step? (Nonsense?) It’s because you can get the answer without adding a number.

So, the boundary of recursion is that there is only one number.

So, with the boundary of recursion, then the recursive formula Woolen cloth? In fact, the recursive formula is implicit in the manual calculation process:

where is the sum of two numbers, and F is the recursive function that finds the sum of multiple numbers. The code is as follows:

#includeusing namespace std;
int F(int a[],int start,int end){ if(start==end)//递归边界
return a[start];
return a[start] + F(a,start+1,end);//递归公式}
int main(){ int a[] = {1,2,3,4,5}; int s=0,e=4; cout << F(a,s,e) << endl;
return 0;
}

4. Find the maximum value of an array element

What is the process of manually finding the maximum value? Traverse and compare. The process is as follows:

For example, find 3,2,6,7, The maximum value of 2 and 4: first set the maximum value max=-999999, and then compare max and array elements one by one (traverse). If a[i]>max, update the value of max to a[i], otherwise max will not Change, continue to traverse backward until the end of the traversal.

max3d30ae069e750146c70360b34343a24f2, max=3 remains unchanged

maxdcbd1e0acf250731439b491204fd0ef42, max=7 remains unchanged

max>4, max=7 remains unchanged

The traversal ends, max=7 is the maximum value.

Similar to summation, the recursive formula is as follows:

where max is the larger value function of two numbers, F It is a recursive function that finds the maximum value of multiple numbers. The code is as follows:

#includeusing namespace std;
#define max(a,b) (a>b?a:b)
int F(int a[],int s,int e){ if(s==e) return a[s]; else if(s+1 == e)//递归边界
return max(a[s],a[e]);
return max(a[s],F(a,s+1,e));//递归公式!!!}
int main(){ int a[] = {5,1,4,6,2}; int s = 0,e = 4; cout << F(a,s,e) << endl;
return 0;
}

The reason why the above examples are [simple examples] is because all the above recursions belong to [one-way recursion] .One-way recursion, the recursive path is one direction, so the idea is relatively easy to think of.

Difficult recursion problems are generally not one-way recursion, but require the use of [backtracking] method, recursion The method is not easy to think of.

The above is the detailed content of What is recursion in c language? Classic recursive function example sharing. For more information, please follow other related articles on the PHP Chinese website!