CS1103 Discussion Assignment Unit 2 - When to use recursive algorithms?

Posted on | In | Views
CS1103 Discussion Assignment Unit 2.

Questions

When should you consider using recursive algorithms when writing a program? Discuss in terms of advantages and disadvantages.

1. Definition of recursion

“A recursive method is a method that calls itself” (Seiter & Palmer, 2019). A recursive method usually consists of two parts: one is the base case, which halts the recursion; the other is the recursive call, that is, calling the method itself inside the method. “Every recursive method must have at least one base case” (Seiter & Palmer, 2019). If a recursive method has no base case, then the recursion is called infinite recursion. This method will call itself repeatedly until the program eventually crashes.

Codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * This is infinite recursion, because it has no base case.
 * The program will crash with a StackOverflowError.
 *
 * @author Zhiyao He
 */
public class RecursivePrintHello {
    public static void printHello() {
        // Part 1: Base case.
        // No base case to halt the recursion.

        System.out.println("hello");

        // Part 2: Call itself
        printHello();
    }

    public static void main(String[] args) {
        printHello();
    }
}

Outputs:

1
2
3
4
5
6
7
8
hello
hello
hello
Exception in thread "main" java.lang.StackOverflowError
	at java.base/sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:554)
	at java.base/java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:585)
	at java.base/sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:293)
	at java.base/sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:282)

For example, in the above program, the printHello() method calls itself internally, so printHello() is a recursive method. However, since this recursive method lacks a base case, it is called infinite recursion. Due to the lack of a base case to stop the recursion, the printHello() will crash with a StackOverflowError.

2. Scenarios suitable for using recursive algorithms

“Recursion is most useful when it is used to solve problems where the structure of the problem repeats” (Seiter & Palmer, 2019). For example, we can use recursion to calculate Fibonacci numbers, which is defined by the recurrence relation: f0 =0; f1 =1; fn = fn-1 + f n-2, for n>1.

According to Seiter & Palmer, “any recursive solution could be written with iteration (loops) instead” (2019). So, in what scenarios is recursion used, and what problems are suitable for iteration? Generally speaking, “iteration is usually preferred and more efficient, but recursive solutions can be elegant and require less code” (Downey & Mayfield, 2019, p. 127).

To further illustrate when recursive algorithms should be considered when writing programs, I will give an example that uses recursion and iteration to calculate Fibonacci numbers. Then, I will illustrate the recursion‘s pros and cons by comparing the two algorithms’ code size and time complexity.

Codes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Calculate Fibonacci numbers using Recursion and Iteration, respectively.
 * Record and compare the times for these two different algorithms?
 * Fibonacci numbers, which is defined by the recurrence relation: f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2), for n>1.
 *
 * @author Zhiyao He
 */
public class IterativeRecursiveFibonacci {
    /**
     * Recursive code
     * This code snippet was written by Amit Shekhar and revised by Zhiyao He
     *
     * @param n
     * @return Fibonacci number
     */
    public static int recursiveFibonacci(int n) {
        // base case
        if (n <= 1) {
            return n;
        }
        // recursive call
        return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
    }

    /**
     * Iterative Code
     * This code snippet was written by Amit Shekhar and revised by Zhiyao He
     *
     * @param n
     * @return Fibonacci number
     */
    public static int iterativeFibonacci(int n) {
        int c = 0;

        // f(0) = 0; f(1) = 1;
        if (n <= 1) {
            return n;
        }

        // f(n) = f(n-1) + f(n-2), for n>1
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }

        return c;
    }

    /**
     * Call the recursive and iterative method, and record the time.
     *
     * @param args
     */
    public static void main(String[] args) {
        long startTime;
        long runTime;
        int result;

        // Record the recursive time
        startTime = System.nanoTime();
        result = recursiveFibonacci(20);
        runTime = System.nanoTime() - startTime;
        System.out.println("RecursiveFib runtimes: " + runTime + " ns" + "; result: " + result);

        // Record the iterative time
        startTime = System.nanoTime();
        result = iterativeFibonacci(20);
        runTime = System.nanoTime() - startTime;
        System.out.println("Iterative runtimes: " + runTime + " ns" + "; result: " + result);
    }
}

Outputs:

1
2
3
4
recursiveFibonacci() runtimes: 424100 ns; result: 6765
iterativeFibonacci() runtimes: 2500 ns; result: 6765

Process finished with exit code 0

In the above example, the pros and cons of using recursion are clear. On the one hand, we can see that the recursive method recursiveFibonacci() is more concise than the iterative method iterativeFibonacci(). In other words, recursiveFibonacci() has less code than iterative Fibonacci(). This is the advantage of recursion. On the other hand, when calculating the Fibonacci number f(20), recursion takes 424100 ns, and iteration takes 2500 ns. Therefore, recursion requires more time than iteration in this case, which is “because the call stack is so heavily used during recursion” (Stack Overflow, n.d.). This is the disadvantage of recursion.

3. In Conclusion

In general, recursion is more elegant and requires less code than iteration, but in some cases, it may take longer to run because recursion requires a lot of call stacks. Hence, if we seek code simplicity, recursion may be a better choice than iteration; if we pursue a faster running time, iteration may be better than recursion.

Word count: 853

References

1.Seiter, L., & Palmer, D. (2020). Introduction to Programming with Java.
https://runestone.academy/runestone/books/published/csjava/index.html

2.Eck, D. J. (2019). Introduction to Programming Using Java.
http://math.hws.edu/javanotes

3.Downey, A. B., & Mayfield, C. (2019). Think Java (2nd ed.). Green Tea Press.

4.Are recursive methods always better than iterative methods in Java? (n.d.). Stack Overflow.
https://stackoverflow.com/questions/15346774/are-recursive-methods-always-better-than-iterative-methods-in-java

​

This is the ending, thanks for reading.