Explore the differences, connections, advantages and disadvantages between recursion and iteration, and compare examples

1. Concept differentiation

The basic concept of recursion: the programming technique of a program calling itself is called recursion, and the function calls itself.

A method in which a function calls itself directly or indirectly in its definition, usually to solve a large complex problem into a smaller problem similar to the original problem, which can greatly reduce the amount of code. Recursion is the ability to define an infinite collection of objects in finite statements.

There are two things to note when using recursion:

1) Recursion is calling itself from within a procedure or function;

2) When recursion is used, there must be an explicit recursive end condition, called a recursive exit.

Recursion is divided into two stages:

1) Recursion: to push the solution of a complex problem to a simpler problem than the original problem;

2) Regression: after obtaining the simplest case, return step by step to obtain complex solutions in turn.

Using recursion can solve a lot of problems: such as knapsack problem, Hannotta problem,… And so on.

Fibonacci numbers are listed as :0,1,1,2,3,5…

Since recursion causes a series of function calls, and there may be a series of repeated calculations, recursive algorithms are relatively inefficient to perform.

Iteration: Use the original value of a variable to deduce a new value of the variable. If recursion calls itself, iteration is A calling B over and over again.

2. Look at recursion and iteration dialectically

Recursion simply means that the application itself calls itself to query and access hierarchical data structures. Recursion can make code cleaner and more readable (not necessarily for beginners), but since recursion requires a system stack, it can consume more space than non-recursive code, and if the recursion is too deep, the system may run out of resources.

There is often a view that there is no need to recurse if there is no need to recurse, and recursion can be replaced by iteration.

Of course, in theory, recursion and iteration are equivalent in terms of time complexity (without considering function call overhead and the function call stack overhead), but in fact recursive efficiency is lower than the iterative indeed, in this case, recursive without any advantage, so does, not necessary to use recursion, then what’s the meaning of the existence of the recursion?

The existence of all things needs the test of time, recursion is not buried by history, that is, there is a reason for existence. In theory, all recursive functions can be converted to iterative functions and vice versa, but the cost is usually high. But from the point of view of algorithm structure, recursively declared structure can not always be transformed into iterative structure, the reason is that the extension of structure itself belongs to the concept of recursion, the iterative method can not be realized at the initial stage of design, just like dynamic polymorphism can not always be realized by static polymorphism method. In the structural design, which is why usually adopts the recursive method rather than with the method of iteration, a very typical example is similar to the linked list, recursive definition and its easy to use, but for the definition of memory (array) the definition and the call processing becomes very difficult, especially in the chain, figure, the problems such as grid, Using an iterative approach becomes impractical both in terms of description and implementation. So practically all iterations can be converted to recursion, but recursion can not necessarily be converted to iteration.

The prerequisite for using a recursive algorithm is that a recursive algorithm can be used if and only if there is expected convergence; otherwise, the recursive algorithm cannot be used.

Recursion is actually convenient for programmers to machine, recursion can be easily converted into programs through mathematical formulas. Its advantage is that it is easy to understand and easy to program. However, recursion is implemented by the stack mechanism, each deep layer, will occupy a piece of stack data area, for some algorithms with deep nested layers, recursion will be inadequate, the space will end up in memory crash, and recursion also brings a lot of function calls, which also has a lot of extra time overhead. So at great depths, it’s not spacetime very good.

Although iteration is efficient, the running time increases only because the number of cycles increases, there is no extra overhead, and there is no increase in space, but the disadvantage is that it is not easy to understand, difficult to write complex problems.

Therefore, “can not need recursion does not need recursion, recursion can be replaced by iteration” such understanding, or dialectical to view, can not be killed. * /

1,2 parts from the network, slightly changed, pay tribute to the original author!

3. Personal summary

Examples are as follows:

#include <iostream>
using namespace std;

// Implement the Fibonacci sequence iteratively
long fab_iteration(int index)
{
	if(index == 1 || index == 2)
	{
		return 1;
	}
	else
	{
		long f1 = 1L;
		long f2 = 1L;
		long f3 = 0;
		for(int i = 0; i < index2 -; i++)
		{   
			f3 = f1 + f2; // Use the original value of the variable to deduce a new value of the variable
			f1 = f2;
			f2 = f3;
		}
		 returnf3; }}// Fibonacci numbers are implemented recursively
 long fab_recursion(int index)
 {    
	if(index == 1 || index == 2)
	{
		return 1;
	}
	else
	{
		return fab_recursion(index- 1) +fab_recursion(index2 -);    // evaluate recursively}}int main(int argc, char* argv[])
{
	cout << fab_recursion(10) << endl;
	cout << fab_iteration(10) << endl;
	return 0;
}
Copy the code