Recursive and non recursive transformation

recursive

Three kinds of problems solved by recursion ：

1. Data is defined recursively .（Fibonacci function ,n The factorial ）
2. The solution of the problem is realized recursively .（ to flash back ）
3. The structural form of data is defined recursively .（ Traversal of binary tree , Figure search ）

The problem of recursion versus loop iteration ：

1. Recursive too deep , Cause stack overflow （ Linear recursion ）
2. Performance issues ( Now compiler optimization is getting better and better , This issue has become relatively less important )

---

Take the Fibonacci series for example

Linear recursion

long long Fib(size_t N)
{
     
	if(N < 3)
		return 1;
	return Fib(N-1) + Fib(N-2);
}

Every time you call, you call first Fib(n-1), Call again Fib(n-2), So the first column in the figure is the first to be called , Because space is not cumulative , The space complexity is calculated by the first column with the largest number O(N)

---

Call recursively before calling Fib(n-1) When ,Fib(n-2) Not implemented yet , You need to save the previous state , Therefore, the cost is large

Tail recursion

int Fib(int n, int ret1, int ret2)
{
     
   if (n == 0)
       return ret1;
   else 
       return Fib(n-1, ret2, ret1 + ret2);
}

1. The criterion of tail recursion is whether the last step of function operation calls itself , Not whether to call itself on the last line of the function
2. In general, tail recursion mainly passes the results of the last run through parameters
3. Spatial complexity O(1)

The importance of a tail call is that it does not add a new stack frame to the call stack —— It's about updating it , Like iteration . The tail has two characteristics due to successive attribution ： Call its own function (Self-called); Computation takes only constant stack space (Stack Space). And formally, as long as it is the last return Statement returns a complete function , It's tail recursion .

Recursive to non recursive

Loop iteration

Tail recursion
Example ： data structure ---- Sort Medium Merge sort non recursive solution

Stack or queue + Loop iteration

Linear recursion
Example ： data structure ---- Sort Medium Quick sort non recursive solution