# C Programming Examples using Recursion

## 1. C Examples on Traversal of a Tree using Recursion

To traverse means to visit the vertices in some systematic order. preorder: visit each node before its children. postorder: visit each node after its children. inorder (for binary trees only): visit left subtree, node, right subtree. Depth first search is a way of traversing graphs, which is closely related to preorder traversal of a tree. The following programs demonstrate the DFS traversal of a tree, common tree traversals using recursion. They also demonstrate reversal of a stack and finds the length of string using recursion.

## 2. C Examples on Sorting Algorithms using Recursion

The Merge Sort follows the Divide and Conquer rule where in it divides the input array into two halves, sorts the two halves and merges the two sorted halves. In Selection Sort, we repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array. A Fibonacci number is the number in which the first two numbers are 1 and 1 and the succeeding number is the sum of the two preceding numbers. The following programs show the implementation of Merge Sort, Selection Sort and Finding the Nth Fibonacci numbers. The program also performs Matrix Multiplication.

## 3. C Examples on Linked List Implementation using Recursion

A Linked List is a dynamic data structure which contains memory blocks occupying random memory locations. The elements in the linked list are called nodes.The programs count the number of occurrences of an element in the linked list using recursion, determines the length of the linked list using recursion and prints the nodes in a linked list using recursion and without using recursion.

## 4. C Examples to illustrate Binary Search Algorithm and Tower of Hanoi Problem using Recursion

The Quick Sort selects an element as a pivot and partitions the given array around the pivot. The Binary Search Algorithm follows the Divide and Conquer strategy where in it finds the item from the sorted list of items. A Palindrome is a string of characters which read the same forward and backward. The programs in the section demonstrate Binary Search, Quick Sort and determine if the given string is a Palindrome or not. It also demonstrates the reverse operation where it reverses the string entered by the user. It also copies the contents of one string into another using recursion. The tower of hanoi is a mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. We have to obtain the same stack on the third rod. The C Program uses recursive function & solves the tower of hanoi.

## 5. C Examples on Basic Mathematical Operations using Recursion

A number is said to be prime if it is divisible by 1 and itself only. GCD of two integers is the largest positive integers that divides the two integers with remainder as 0 and LCM of two integers is the smallest positive integer that is the multiple of both the integers. A factorial is a function that multiplies a number by every number below it. Multiplying a number by itself gives the power of a number. The H.C.F. of two or more than two numbers is the greatest number that divides each of them exactly. The following programs determine if a number is prime or not, calculate the factorial, LCM, HCF, GCD and Power of the given numbers.

## 6. C Examples on Number System Conversion using Recursion

The programs in the following section deals with the number system in mathematics. The binary equivalent of a number contains a set of 0’s and 1’s.The programs performs conversion of a number in decimal system to a number in binary system and print the binary equivalent of the number.It also prints the alternate nodes of a linked list.