Headline

An algorithm for transforming recursive into iterative functions

Illustration

Each recursive function can be transformed into an equivalent non-recursive function, subject to using iterative constructs and possibly extra data structures for simulating the call stack. Depending on programming language and form of recursion, different algorithms can be applied.

Consider the following recursive formulation of factorial:

	public static long factorial(int n) {
		if (n <= 1)
			return 1;
		else
			return n * factorial(n - 1);
	}	

There are various iterative forumulations of factorial. There are different approaches towards deriving an iterative formulation from a recursive. The following example illustrates how single recursion can be transformed into iteration while a stack is used to keep track of variables for each call frame.

	// Abstract program pointer
	public enum Pointer {
		calling, returning
	};

	public static long factorial(int n) {
		int r = 0; // Result
		Stack s = new Stack(); // Prepare call stack
		Pointer p = Pointer.calling;
		do
			switch (p) {
			case calling:
				if (n <= 1) {
					// Return from base case
					r = 1;
					p = Pointer.returning;
				} else {
					// Recursive call
					s.push(n); // Backup call frame
					n = n - 1; // Compute argument
				}
				break;
			case returning:
				// Return from recursive call
				n = (int) s.peek(); // Restore variables
				s.pop(); // Destroy call frame
				r = n * r; // Use recursive result
				break;
			}
		while (!(s.isEmpty()));
		return r;
	}

The original function only uses one local variable n for the argument of the function. Thus, the simulated call stack maintains ints, indeed. If a function had additional local variable declarations, then these would need to be pushed together in one record. The iterative formulation loops as long as the call stack is not empty while the loop's body is executed at least once for the base case. The loop can be in two modes: calling or returning. In calling mode, the parts of the function for the base case or prior to a recursive call are evaluated. In returning mode, the parts of the function past a recursive call are evaluated. In this sense, the mode and the switch statement on it can be seen as the abstract model of a program pointer: the pointer points to the beginning of a function or the remaining operations past the recursive call.


There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.