What is the difference between recursion and iteration in Java?

1. The difference between recursion and iteration

• When an entity calls itself , the program is called recursive.

• When there is a loop (or repetition) , the program is called an iterative call .

• Example: Program to find the factorial of a number

## Time complexity comparison

• The time complexity of finding recursion is more difficult than that of iteration.

• Recursion: The time complexity of recursion can be found by finding the value of the nth recursive call based on the previous calls. Therefore, finding the target case based on the base case, and solving it based on the base case, allows us to understand the time complexity of the recursive equation.

• Iteration: The time complexity of an iteration can be found by finding the number of loops repeated within the loop.

Usage comparison

• Using any of these techniques is a trade-off between time complexity and code size trade-off.

• If time complexity is the focus and the number of recursive calls will be large, it is best to use iteration.

• However, if time complexity is not an issue and code shortness is, then recursion would be the way to go.

• Recursion: Recursion involves calling the same function again, so the code length is very short. However, as we saw in our analysis, the time complexity of recursion can grow exponentially when the number of recursive calls is considerable. Therefore, the use of recursion is advantageous in shorter code, but at a higher time complexity.

• Iteration: Iteration is the repetition of a block of code. This involves a larger amount of code, but the time complexity is usually lower than recursion.

Overhead

• Recursion has a lot of overhead compared to iteration.

• Recursion: Recursion has the overhead of repeated function calls, that is, due to repeated calls to the same function, the time complexity of the code Increased many times.

• Iteration: Iteration does not involve any such overhead.

Infinite Repetition

• Infinite Repetition in recursion will cause CPU crash, but in During the iteration, it stops when memory is exhausted.

• Recursion: In Recursion, infinite recursive calls may occur due to errors in the specified basic conditions, and continuous calls will never be false. function, which may cause the system CPU to crash.

• Iteration: Infinite iteration due to an iterator assignment or increment error or a termination condition error will result in an infinite loop, which may or may not cause the system to Error, but will definitely stop further execution of the program.

DefinitionApplyTerminationUsageCode sizeTime complexitySpace complexityHeapSpeedStorageElevatedInfinite Repeat2. Code

##Recursion	Iteration
The function calls itself.	A set of instructions that are executed repeatedly.
for functions.	For loops.
Through the base case, there will be no function calls here.	When the iterator's termination condition is no longer met.
Use when code size needs to be small and time complexity is not an issue.	Use when time complexity needs to be balanced against expanded code size
Less code	More code
Very high (usually exponential) time complexity.	The time complexity is relatively low (generally polynomial-logarithm).
The space complexity is higher than iteration.	The space complexity is low.
The stack here is used to store local variables when functions are called.	Do not use the stack.
Execution is slow because it has the overhead of maintaining and updating the stack.	Generally, it is faster than recursion because it does not use the stack.
Recursion uses more memory compared to iteration.	There is no overhead because there are no function calls in the iteration.
Have the overhead of repeated function calls.	There is no overhead because there are no function calls in the iteration.
If a recursive function does not satisfy the termination condition or is undefined or the base case is never reached, it will result in a stack overflow error and the system may run indefinitely Crash in recursion.	If the control condition of the iteration statement is never false or the control variable does not reach the terminal value, it will cause an infinite loop. In an infinite loop, it uses CPU cycles again and again.

public class Test {
    // ----- 递归 -----
    // 求给定数的阶乘的方法
    static int factorialUsingRecursion(int n)
    {
        if (n == 0)
            return 1;

        // 递归呼叫
        return n * factorialUsingRecursion(n - 1);
    }

    // -----迭代 -----
    //求给定数的阶乘的方法
    static int factorialUsingIteration(int n)
    {
        int res = 1, i;

        // 迭代
        for (i = 2; i <= n; i++)
            res *= i;

        return res;
    }

    public static void main(String[] args)
    {
        int num = 5;
        System.out.println("Factorial of " + num
                + " using Recursion is: "
                + factorialUsingRecursion(5));

        System.out.println("Factorial of " + num
                + " using Iteration is: "
                + factorialUsingIteration(5));
    }
}

Factorial of 5 using Recursion is: 120
Factorial of 5 using Iteration is: 120

The above is the detailed content of What is the difference between recursion and iteration in Java?. For more information, please follow other related articles on the PHP Chinese website!