De-recursive

In computer science, de- recursive refers to the conversion of a recursive function into an iterative function .

Recursions are a technique that is often used in computer science to define a function by itself. For this, the recursive function first partially solves the given problem or divides it into several sub-problems and then calls itself with these new sub-problems. This continues until the problem is completely resolved or the solution is broken down into trivial individual parts.

Recursive solutions are often more elegant and easier to find and easier to check for correctness (e.g. by means of mathematical induction ) than iterative functions, but are less efficient due to the many function calls depending on the programming language used , which is why it is with performance-critical program parts often it pays to de-recursive a recursive function. Since recursions and iterative functions are equally powerful, there is an iterative equivalent for each recursion.

Resolve linear recursion

Linear recursions are recursions in which there is a maximum of one recursion call per recursion step. The calculation runs along a chain of calls. Linear recursions are very easy to resolve. As an example, a recursive function that calculates the factorial of a number.

int fac(int x) {
	if (x = 0) {
		return 1;
	} else {
		return x * fac(x - 1);
	}
}

The first thing that is necessary here is to reduce the separate return values ​​to one return value:

int fac(int x) {
	int value;
	if (x = 0) {
		value = 1;
	} else {
		value = x * fac(x - 1);
	}
	return value;
}

Finally, the return command is replaced by an accumulator and the recursion by a loop:

int fac(int x) {
	int accumulator = 1;
	bool running = true;
	while (running) {
		int value;
		if (x = 0) {
			value = 1;
			running = false; //Hier endet die Rekursionskette
					 //im ursprünglichen Algorithmus.
					 //Äquivalent zu return(1);
		} else {
			value = x;
			x = x-1;	 //Hier geht die Rekursionskette weiter.
			running = true;	 //Äquivalent zu return x*fac(x-1);
		}
		accumulator = accumulator * value;
	}
	return accumulator;
}

This function can then be further optimized by omitting unnecessary assignments that were created by the conversion.

Individual evidence

1. ↑ G. Pomberger, H. Dobler: Algorithms and data structures . Retrieved June 17, 2014.
2. ↑ Algorithms and Data Structures 04 (PDF). Technical Faculty of the University of Erlangen; Retrieved June 17, 2014.
3. ↑ Algorithms and data structures 06 Decursive  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. (PDF). Institute for Information Systems and Software Engineering at the University of Linz; Retrieved June 17, 2014.  
4. ↑ H. Peter Gumm: Programming and Proof . (PDF) Retrieved June 17, 2014.