Iteration via recursion

Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.

c go java js lua py vbs rkt scm pro

It is well known that limited iteration can be done without a loop.

In the message passing model of function calls, we will create a program using iteration without a loop, then abstract parts to a function, then the function will pass messages to itself using the message passing model.

Recursive rules apply to parts of imperative programs, though it is not as obvious.

Consider the while loop defined in pseudo-code as follows.

while b do S end while

The above while loop can be defined (as in a macro expansion) as follows.

if b then S while b do S end while end if

The expansion can go on until the while loop is complete. This is sometimes call loop unrolling (in, say, code optimization techniques).

Consider the following declarations of a string and an integer position.

char s1[256];
int pos1 = 0;

One can read up to 4 strings with the following iteration without a loop.

if (gets(s1)) {
	pos1++;
	printf("%d. %s\n",pos1,s1);
	if (gets(s1)) {
		pos1++;
		printf("%d. %s\n",pos1,s1);
		if (gets(s1)) {
			pos1++;
			printf("%d. %s\n",pos1,s1);
			if (gets(s1)) {
				pos1++;
				printf("%d. %s\n",pos1,s1);
				}
			}
		}
	}

Consider the following program that inputs up to 4 lines of text without a loop.

Here is the C code.

#include <stdio.h>
#include <string.h>

int main() {
	char s1[256];
	int pos1 = 0;
	if (gets(s1)) {
		pos1++;
		printf("%d. %s\n",pos1,s1);
		if (gets(s1)) {
			pos1++;
			printf("%d. %s\n",pos1,s1);
			if (gets(s1)) {
				pos1++;
				printf("%d. %s\n",pos1,s1);
				if (gets(s1)) {
					pos1++;
					printf("%d. %s\n",pos1,s1);
					}
				}
			}
		}
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

one
two
three
four

For the above example input, here is the expected output.

1. one
2. two
3. three
4. four

Let us abstract the above program to move the iteration without a loop to a procedure called doWhile1. The string s1 is passed (by reference) and the position passed (by value).

Here is the C code.

#include <stdio.h>
#include <string.h>

void whileDo1(char *s1, int pos1) {
	if (gets(s1)) {
		pos1++;
		printf("%d. %s\n",pos1,s1);
		if (gets(s1)) {
			pos1++;
			printf("%d. %s\n",pos1,s1);
			if (gets(s1)) {
				pos1++;
				printf("%d. %s\n",pos1,s1);
				if (gets(s1)) {
					pos1++;
					printf("%d. %s\n",pos1,s1);
					}
				}
			}
		}
	}

int main() {
	char s1[256];
	whileDo1(s1,0);
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

one
two
three
four

For the above example input, here is the expected output.

1. one
2. two
3. three
4. four

Note that according to the definition of a while loop, the second conditional can be made to call the doWhile1 itself. This results in the following program, which is no longer limited to 4 iterations.

Thus, recursion can be used to avoid the use of the while or for loop. This is what is done in functional languages. Here is the C code.

#include <stdio.h>
#include <string.h>

void whileDo1(char *s1, int pos1) {
	if (gets(s1)) {
		pos1++;
		printf("%d. %s\n",pos1,s1);
		whileDo1(s1,pos1);
		}
	}

int main() {
	char s1[256];
	whileDo1(s1,0);
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

one
two
three
four

For the above example input, here is the expected output.

1. one
2. two
3. three
4. four