## Recursion in C

**By:** Ivan Lim **Viewed:** 1387 times Printer Friendly Format

C functions may be used recursively; that is, a function may call itself either directly or indirectly. Consider printing a number as a character string. As we mentioned before, the digits are generated in 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 are generated, then print them in the reverse order. The
alternative is a recursive solution, in which `printd` first calls itself
to cope with any leading digits, then prints the trailing digit. Again, this
version can fail on the largest 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 automatic 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 in turn passes

`1`to a third. 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 good example of recursion is quicksort, a sorting algorithm developed by C.A.R. Hoare in 1962. Given an array, one element is chosen and the others partitioned in two subsets - those less than the partition element and those greater than or equal to it. The same process is then applied recursively to the two subsets. When a subset has fewer than two elements, it doesn't need any sorting; this stops the recursion.

Our version of quicksort is not the fastest possible, but it's one of the simplest. 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; }The standard library includes a version of

`qsort`that can sort objects of any type.

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 and understand than the non-recursive equivalent. Recursion is especially convenient for recursively defined data structures like trees.

Comment on this tutorial

- Android
- AJAX
- ASP.net
- C
- C++
- C#
- Cocoa
- Cloud Computing
- HTML5
- Java
- Javascript
- JSF
- JSP
- J2ME
- Java Beans
- EJB
- JDBC
- Linux
- Mac OS X
- iPhone
- MySQL
- Office 365
- Perl
- PHP
- Python
- Ruby
- VB.net
- Hibernate
- Struts
- SAP
- Trends
- Tech Reviews
- WebServices
- XML
- Certification
- Interview

#### categories

#### Subscribe to Tutorials

#### Related Tutorials

Sum of the elements of an array in C

Printing a simple histogram in C

Find square and square root for a given number in C

Simple arithmetic calculations in C

Passing double value to a function in C

Passing pointer to a function in C

Infix to Prefix And Postfix in C

while, do while and for loops in C