Recursion in C

By: Ivan Lim Emailed: 1607 times Printed: 2075 times    

Latest comments
By: rohit kumar - how this program is work
By: Kirti - Hi..thx for the hadoop in
By: Spijker - I have altered the code a
By: ali mohammed - why we use the java in ne
By: ali mohammed - why we use the java in ne
By: mizhelle - when I exported the data
By: raul - no output as well, i'm ge
By: Rajesh - thanx very much...
By: Suindu De - Suppose we are executing

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.


C Home | All C Tutorials | Latest C Tutorials

Sponsored Links

If this tutorial doesn't answer your question, or you have a specific question, just ask an expert here. Post your question to get a direct answer.



Bookmark and Share

Comments(0)


Be the first one to add a comment

Your name (required):


Your email(required, will not be shown to the public):


Your sites URL (optional):


Your comments:



More Tutorials by Ivan Lim
Requesting a Signed Certificate from a Certification Authority example using keytool in Java
The if-then Statement in Java
SELECT Statements
The BodyTag Interface in JSP
Handling Duplicate Form Submissions in Struts
Standard Input and Output in C
A sample that shows Java Beans, Servlets and JSP working together
Recursion in C
Using Multibox in Struts
switch in C
Word Counting sample program in C
Java Bean Scopes in JSF
Using cout.width() in C++
Types of configurations in J2ME
How to get the CLDC and MIDP version from a J2ME program

More Tutorials in C
Sum of the elements of an array in C
Printing a simple histogram in C
Sorting an integer array in C
Find square and square root for a given number in C
Simple arithmetic calculations in C
Command-line arguments in C
Calculator 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
Unicode and UTF-8 in C
Formatting with printf in C
if, if...else and switch statements in C with samples
Statements in C

More Latest News
Most Viewed Articles (in C )
Using memset(), memcpy(), and memmove() in C
Listing Files and Directories sample program in C
perror() Function - example program in C
Open, Creat, Close, Unlink system calls sample program in C
UNIX read and write system calls sample program in C
Using free() Function in C
assert() Function Example program in C
scanf and sscanf sample program in C
Sum of the elements of an array in C
Printing a simple histogram in C
lseek() sample program in C
Sorting an integer array in C
Find square and square root for a given number in C
Functions in C
goto and labels in C
Most Emailed Articles (in C)
Address Arithmetic and pointers in C
Macro Substitution using #define in C
Pointers to Structures example program in C
Getting Started with C
Variables and Arithmetic Expressions in C
register Variables in C
Trigonometric, Hyperbolic, Exponential and Logarithmic Functions in C
Printing a simple histogram in C
Symbolic Constants using #define in C
Arguments - Call by Value in C
Conditional Expressions in C
Functions returning non-integer values in C
Recursion in C
Tutorial on Complicated Declarations in C
Standard Input and Output in C