## What Is Recursion

C functions could also be used recursively; that’s , a function may call itself either directly or indirectly. Consider printing variety as a personality string. As we mentioned before, the digits are generated within the wrong order:

low-order digits are available before high-order digits, but they have to be printed the other way around.

There are two solutions to this problem. On is to store the digits in an array as they’re

generated, then print them within the reverse order.

The alternative may be a recursive solution, during which printd first calls itself to deal with any leading digits, then prints the trailing digit. Again, this version can fail on the most important negative number.

#include<stdio.h> /* printd: print n in decimal */ void printd(int n) { if (n < 0) { putchar('-'); n = -n; } if (n / 10) printd(n / 10); putchar(n % 10 + '0'); }

When a function calls itself recursively, each invocation gets a fresh set of all the automated variables, independent of the previous set.

This in printd(123) the first printd receives the argument n = 123. It passes 12 to a second printd, which successively passes 1 to a 3rd . The third-level printd prints 1, then returns to the second level.

That printd prints 2, then returns to the first level. That one prints 3 and terminates.

Another example of recursion is quicksort, a algorithm developed by C.A.R. Hoare in 1962.

Given an array, one element is chosen and therefore the others partitioned in two

subsets – those but the partition element and people greater than or adequate to it. The same process is then applied recursively to the 2 subsets.

When a subset has fewer than two elements, it doesn’t need any sorting; this stops the recursion.

Our version of quicksort isn’t the fastest possible, but it’s one amongthe only. We use the middle element of each subarray for partitioning.

/* qsort: sort v[left]…v[right] into increasing order */ void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if (left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right)/2); /* move partition elem */ last = left; /* to v[0] */ for (i = left + 1; i <= right; i++) /* partition */ if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); /* restore partition elem */ qsort(v, left, last-1); qsort(v, last+1, right);

We moved the swapping operation into a separate function swap because it occurs three times in qsort.

/* swap: interchange v[i] and v[j] */ void swap(int v[], int i, int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; }

Recursion may provide no saving in storage, since somewhere a stack of the values being

processed must be maintained.

Nor will it be faster. But recursive code is more compact, and often much easier to write down and understand than the non-recursive equivalent.

If you like this post, don’t forget to share 🙂

## No Comments

Leave a comment Cancel