free estadisticas Saltar al contenido

Difference between recursion and iteration

marzo 18, 2020

Recursion and iteration repeatedly execute the instruction set. Recursion when an instruction in a function is called repeatedly. Iteration occurs when a loop is repeatedly executed until the check condition becomes false. The main difference between recursion and iteration that the recursion a process, always applied to a function. L' iteration it is applied to the set of instructions we want to execute repeatedly.

Comparative chart

Basis for the confrontation Iteration
BasicThe statement in a body of functions calls the function itself.Allows you to repeatedly execute the instruction set.
FormatIn recursive function, only the termination condition is specified (base case).The iteration includes initialization, condition, execution of the instruction within the cycle and updating (increments and decrements) of the control variable.
endA conditional statement included in the function body to force the function to return without the recursion call being made.The iteration instruction is repeatedly executed until a certain condition is reached.
ConditionIf the function does not converge into a condition called (base case), it leads to infinite recursion.If the check condition in the iteration declaration never becomes false, it leads to an infinite iteration.
Endless repetitionInfinite recursion can crash the system.The infinite loop repeatedly uses CPU cycles.
AppliedRecursion always applied to functions.The iteration is applied to iteration instructions or "loops".
StackThe stack is used to store the set of new local variables and parameters each time the function is called.It does not use the stack.
upRecursion has the overhead of repeated function calls.No overhead of repeated function calls.
speedSlow running.Fast running.
Code sizeRecursion reduces the size of the code.Iterating makes the code longer.

Definition of recursion

C ++ allows a function to call itself within its code. This means that the function definition has a function call to itself. Sometimes also called " circular definition ". The set of local variables and parameters used by the function are recreated each time the function calls itself and are stored at the top of the stack. But, each time a function is called, it doesn't create a new copy of The recursive function does not significantly reduce the size of the code and does not even improve memory usage, but it does so with respect to iteration.

To end the recursion, you need to include a select statement in the function definition to force the function to return without giving a recursive call to itself. The absence of the select statement in the definition of a recursive function will allow the infinite recursive function once called.

Let us understand recursion with a function that will return the factorial of the number.

 int factorial (int num) {int answer; if (num == 1) {return 1; } else {answer = factorial (num-1) * num; // chiamata ricorsiva} return (risposta); } 

In the previous code, the statement elsewhere shows the recursion, since the statement calls the factorial () function in which it resides.

Definition of Iteration

Iterating a process that repeatedly executes the set of instructions until the condition in the iteration declaration becomes false. The iteration instruction includes initialization, comparison, execution of instructions within the iteration instruction, and finally updating the control variable. After the control variable has been updated, it is compared again and the process repeats until the condition in the iteration declaration is false. The iteration instructions are "for" loop, "while" loop, "do-while" loop.

The iteration instruction does not use a stack to store variables. Hence, the execution of the iteration instruction is faster than the recursive function. Even the iteration function does not have the overhead of repeated function calls that make its execution faster than the recursive function. The iteration ends when the control condition becomes false. The absence of the control condition in the iteration instruction can cause an infinite loop or can cause a compilation error.

We understand the iteration related to the previous example.

 int factorial (int num) {int answer = 1; // ha bisogno dell'inizializzazione perch potrebbe contenere un valore spazzatura prima della sua inizializzazione per (int t = 1; t> num; t ++) // iterazione {answer = answer * (t); ritorno (risposta); }} 

In the above code, the function returns the factorial of the number using the iteration statement.

Key differences between recursion and iteration

  1. Recursion when a method in a program is called repeatedly while, iterating when a series of instructions in a program is repeatedly executed.
  2. A recursive method contains an instruction set, an instruction call and a termination condition while the iteration instructions contain initialization, increment, condition, instruction set within a loop and a control variable.
  3. A conditional statement decides the end of the recursion and the value of the control variable decides the end of the iteration statement.
  4. If the method does not lead to the termination condition it enters infinite recursion. On the other hand, if the control variable never leads to the termination value, the iteration instruction iterates infinitely.
  5. Infinite recursion can lead to system crashes while infinite iteration consumes CPU cycles.
  6. Recursion is always applied to the method while iteration is applied to the instruction set.
  7. Variables created during recursion are stored on the stack while iteration does not require a stack.
  8. Recursion causes the repeated function call to overhead, while iteration does not have a function that calls overhead.
  9. Due to the feature called overhead, slower recursion execution while faster iteration execution.
  10. Recursion reduces the size of the code while iterations extend the code.

Conclusion:

The recursive function is easy to write, but it doesn't perform well compared to iteration, while the iteration is difficult to write but their performance is good compared to recursion.