Why is recursion so hard to learn

Java-Tutorial.org

Iteration and recursion

Methods can be used both iteratively and recursively. An iteration (lat. Repetition) is understood as the multiple execution of one or more instructions. The iteration is implemented by loops (for, while ..). The loop is ended by means of an abort condition.

We speak of recursion (from the Latin recurrere = to run back) when a method calls itself again and again until a termination condition is met. Each recursion can also be converted into an iterative solution and vice versa.

Iterations have the advantage that they are more efficient. However, a recursion usually gets by with less source code and is clearer, but more memory-intensive. However, recursions are often more difficult for novice programmers to understand.

In the following examples we calculate the factorial of a whole positive number (as a mathematical symbol a "!" After the number) once iteratively and once recursively. Even the definition is recursive: 0! = 1, 1! = 1, (n> 1)! = n * (n-1)!

Here is the iterative solution:

class IterativFakultaet {// method for calculating the faculty staticallong calculateFakultaet (int n) {long facu = 1; // Iterative calculationfor (int i = 1; i <= n; i ++) {faku * = i;} return faku;} publicstaticvoid main (String [] args) {long faku = calculateFacultaet (5); System.out.println ("5! =" + faku);}}


Now let's look at the computation of a factorial using recursion.

class RecursiveFacultaet {staticlong calculateFacultaet (int n) {System.out.println ("call with" + n); if (n> = 1) {// recursive call (calls itself) return n * calculateFacultaet (n-1 );} else {// termination condition of the recursion return1;}} publicstaticvoid main (String [] args) {long faku = calculateFacultaet (5); System.out.println ("5! =" + faku);}}

To clarify the recursion, let's take a closer look at what happens.

if (n> = 1) return n * calculateFaculty (n-1); else return1;

1st call with 5: 5 * calculate faculty (5-1)
2nd call with 4: 5 * 4 * calculateFacultaet (4-1)
3rd call with 3: 5 * 4 * 3 * calculateFacultaet (3-1)
4th call with 2: 5 * 4 * 3 * 2 * calculateFacultaet (2-1)
5th call with 1: 5 * 4 * 3 * 2 * 1 * calculate faculty (1-1)
6. Call with 0: 5 * 4 * 3 * 2 * 1 * 1

The recursion is only ended with the sixth call and then returns the calculated value.

It should not go unmentioned that the example of the faculty is not one that would necessarily be solved recursively in practice. In this case, the loop is not only easier to read, it is also more memory-efficient (each call uses resources!) And its runtime behavior is also significantly better.

So apparently everything speaks against recursions. However, there are also problems that are very difficult (but never impossible!) To solve with loops.

Here are two examples:

1.) One method should find all files in the folder tree in and below the folder specified by the "folder" parameter whose names contain the character string specified in the "substring" parameter.

The problem can be broken down:
i. List the appropriate files in the specified folder
ii. call for each folder in the specified folder.

Step ii creates the recursion, which in this case is much easier to read than any attempt to solve the problem with loops.

2.) The well-known game "Towers of Hanoi", in which a stack of n slices that get smaller from bottom to top (can be represented with an array s [], the data type should not interest us here) from a tower (eg b, c) must be moved to another, whereby a) only one disc may be moved at a time, which b) may never be placed on a smaller disc.

The problem: The lowest disk s [0] should be brought from tower a to tower b. Again, the problem can be broken down:
i. "Park" the disc tower via s [0] (ie s [1] .. s [n-1]) on tower c (this step forms the recursion)
ii. put s [0] on tower b
iii. "Park" the tower and including the in i. parked disc from c to b (this "fetches" the parked tower; this step is also recursive)

In both cases, it is important to think about whether the recursion will come to an end. This is the case in the second example because each tower only has a limited number of discs. In the first, because folder trees cannot be infinitely deep. But be careful: In Unix-like operating systems, for example, so-called "hard links" or "symbolic links" can very well create seemingly endless structures! We just want to make it clear that the devil is often in the details, and that recursions need to be carefully thought out and planned.