Antoun J. Yaacoub Ph.D.

Recursion exercises in C Programming in C

Sum of the first n terms of the harmonic series - recursive: Write a recursive function float harm_rec(int n) which computes the sum of the first n terms of the harmonic series (n is passed in parameter): $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$...
Sum of the terms of the harmonic series and stops when the value of the term added is lower than a positive threshold - recursive: Write a recursive function float harm_rec_threshold(float s, int i) which calculates the sum of the terms of the harmonic series and stops when the value of the term added is lower than a positive threshold s passed in parameter: $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$...
Recursive function to convert a decimal integer to binary: Write a recursive function that converts a decimal integer to binary....
Recursive function to calculate the factorial of a positive integer: Write a recursive function that calculates the factorial of a positive integer....
Recursive function to calculate the binomial coefficient: Write a recursive function that calculates the binomial coefficient. $C_n^p=\frac{n!}{(n-p)!\times p!}$...
Calculate power of a number using recursion: Write a function that calculates $x^y$ using recursion. $$x^y=\Bigg\{\begin{array}{c c c}1&if & y=0\\x \times x^{Y-1} & if & y>0\\ \frac{1}{x^{-y}} & if & y < 0\end{array}$$...
Print a range of integers using recursion: Write a function that prints a range of integers using recursion....
Print even numbers in a range of integers using recursion: Write a function that prints even numbers in a range of integers using recursion....
Print odd numbers in a range of integers using recursion: Write a function that prints odd numbers in a range of integers using recursion....
Sum a range of integers using recursion: Write a function that calculates the sum of a range of integers using recursion....
Sum of even numbers in a range of integers using recursion: Write a function that calculates the sum of even numbers in a range of integers using recursion....
Sum of odd numbers in a range of integers using recursion: Write a function that calculates the sum of odd numbers in a range of integers using recursion....
Reverse a number using recursion: Write a function that calculates the reverse of an integer using recursion....
Check if a number is palindromic a number using recursion: Write a function that checks if a number is palindromic a number using recursion....
Calculate the sum of digits of an integer using recursion: Write a function that calculates the sum of digits of an integer using recursion....
Factorial of a number using recursion: Write a function that calculates the factorial of a number using recursion....
GCD between 2 numbers using recursion: Calculate the gcd between two natural numbers using the EUCLIDE algorithm. Example: gcd(1220,516)=?1220 mod 516 = 188 516 mod 188 = 140 188 mod 140 = 48 140 mod 48 = 44 48 mod 44 = 4 44 mod 4= 0gcd(1220,516)= 4...
LCM between 2 numbers using recursion - version 1: Calculate the lcm between two natural numbers using recursion. Example: lcm(1220,516) ? Multiple of 516 are: 516 1032 1548 2064 ... 157380 ... Multiple of 1220 are: 1220 2440 ... 157380 ... Method 1: Check whether the maximum number clearly divid...
LCM between 2 numbers using recursion - version 2: Calculate the lcm between two natural numbers using recursion. Example: lcm(1220,516) ? Multiple of 516 are: 516 1032 1548 2064 ... 157380 ... Multiple of 1220 are: 1220 2440 ... 157380 ... Method 2: calculate thr common factors of each number, t...
Number of digits in a long integer number using recursion: Write the NUM function of the type int which obtains an integer value N (positive or negative) of the long type as a parameter and which gives the number of digits of N as a result. Write a small program that tests the function NUM. Example: ...
Minimum value of an array using recursive function: Write a recursive function that returns the minimum of an array of integers.Prototype: int min(int tab[], int tab_size)Write a main function to test your program....
Sum of the first N value of an array using recursive function: Write a recursive function that returns the sum of the first N integers of an array.Write a main function to test your program....
Minimum and maximum values of an array using recursive function: Write a recursive function that returns the minimumand the maximum values of an array of integers.Write a main function to test your program....
Checking whether all the elements of an array belong to another array: Write a recursive function that determines whether all the elements of an integer arrayT1 belong to another integer array T2....
Checking whether an array is included in block in another array: Write a recursive function that determines whether an integer array T1 is includedin block in another array of integers T2. It is advisable to write another recursive function that determines whether an integer array T1 begins (is in block at the beg...
Mirror of characters: Write a recursive function void mirror(void) that reads character by character (usingthe function getchar()) a string terminated by ? and then displays the string in reverse order.void main(){ mirror();}...
Checking whether a specific element is in an array: Write a recursive function testing whether a specific element is in an array.Prototype : int in_array(int tab[], int N, int element)Write a main function to test your program....
Calculating the number of occurrences of an element in an array: Write a recursive function that returns the number of occurrences of an element in anarray.Prototype : int nb_occurrence(int tab[], int N, int value)Write a main function to test your program....
Mirroring the elements in an array: Write a recursive function that mirrors the elements in an array.Prototype : void mirror(int tab[], int start, int end)Write a main function to test your program....
Egyptian multiplication: Write a program that takes as input two positive integers A and B, then calls a recursive function that finds the product of A by B using the Egyptian method. The Egyptian method rules are: If B=0 then A*B=0 If B is even then A*B = (2*A) * (B/2) If B...
Recursive function to calculate the Fibonacci sequence: Write a recursive function that calculates the N-th term $U_N$ of the FIBONACCI sequence that is given by the recurrence relation:$U_1=1 \ \ \ U_2=1 \ \ \ U_N=U_{N-1}+ U_{N-2}$ (for N>2)...
Removing a sequence of 3 characters from a string: Write a function Reduction that takes a string S and eliminates from S every sequence of 3 or more consecutive occurrences of the same character. The function returns 1 if it finds at least one sequence to eliminate from S and 0 if no sequence to eli...
Sequence values and ranks: Consider the following sequence defined by: \[ U_0=1 ; U_n= \Big\{\begin{array}{c c c} U_{n-1}^2 & if & \texttt{n is an even number } \\ U_{n-1}+n! & if & \texttt{n is an odd number} \end{array}\] Write a function that takes an intege...
Sorting using merge-sort algorithm: Sort the elements of an array A in ascending order. Condition Merge 2 arrays (each of 1 element) Divide the non sorted array until the condition is verified and sort the divided parts into pairs. Precisely: Recursively divide the non sorted array in...
Sorting using quick-sort algorithm: Sort the elements of an array A in ascending order. Quick-sort uses recursive calls for sorting the elements. Is an example for divide-and-conquer algorithmic technique.Divide: the array A[low … high] is partitioned into two non-empty sub arrays A[...
Maximum value in a Binary tree of integers: Write each time a function that returns the maximum value of all the nodes in a binary tree of integers. Assume all values are nonnegative; return -1 if the tree is empty. recursive function iterartive using a queue iterative using a stack ...
Printing some values of a binary tree of integers: Write a recursive function that prints all the nodes less than a given value $v$ in a binary tree of integers....
Sum of values in a binary tree of integers: Write a recursive function that returns the sum of all the nodes in a binary tree of integers....
Number of nodes in a binary tree of integers: Write a recursive function that counts the number of nodes in a binary tree of integers....
Checking whether an element is in a Binary search tree using recursion: Write a recursive function that tests whether an element belongs to a $BST$....
Checking whether a given binary tree is a BST: Part 1 Write a function that checks whether a given binary tree is a BST or not. Consider the following simple program. For each node, check if the left node of it is smaller than the node and the right node is greater than the node. This approach is...
Write a recursive function that checks whether an element belongs to a BST: Write a recursive function that checks whether an element belongs to a BST....
Checking whether elements of 2 BSTs are the same using recursion: Given 2 BSTs, write a recursive function that checks whether the elements of both BSTs are the same or not. The time complexity of your algorithm should be $O(m\times n)$, where $m$ and $n$ are the numbers of elements in the two BSTs ....
Recursively reverse a stack: Write a recursive function that inserts an element $\texttt{e}$ at the bottom of a stack by using only stack operations.$\textit{Prototype}: \texttt{void InsertAtBottom(Stack *s, element e)}$ Write a recursive function that reverses the elements...
Insert an element and keep the stack sorted: Write a recursive function that inserts an element e in a stack and keeps it sorted. The top element is the smallest one....
Automata: Consider the following declaration:typedef struct { int V; int E; char **Adj; } automata;An $$\texttt{automata}$$ is a directed weighted graph where weights are characters. Write a function that reads and returns an $$\texttt{automata}...
Recursive DFS traversal of a graph using an adjacency list: Perform a recursive DFS traversal over a graph represented using an adjacency list....
Path between two vertices: Write a program that checks whether a path exists between two vertices in a graph. Implement the graph using an adjacency list and use DFS....
Connected graph: Write a program that checks whether a graph is connected. Implement the graph using an adjacency list and use DFS....
Balanced binary trees: A binary tree is said to be balanced if both of its subtrees are balanced and the height of its left subtree differs from the height of its right subtree by at most 1. Write a C function to determine whether a given binary tree is balanced....
Depth and height of binary trees: Write a function that returns the depth/height of a binary tree. ...
Leaf nodes in binary trees: Write a function that counts the number of leaf nodes in a binary tree....
Non Leaf nodes in binary trees: Write a function that counts the number of non-leaf nodes in a binary tree....
Comb left binary trees: A comb left is a locally complete binary tree (each node has 0 or 2 children) in which each right child of a node is a leaf. Write a function $\texttt{isLeftComb}$ that checks if a binary tree is a left comb. **img**isLeftComb.png##img##...
Set of integer in binary search trees: We want to construct a binary search tree to represent a set of integer numbers. Unlike the traditional binary search tree where each node contains only one integer value, we want to allow each node to contain all the values between two bounds $$\tex...
Same elements in binary search trees: Give the declaration of a Binary Search Tree of integers ($$\texttt{BST}$$). Write a recursive function that checks whether an element belongs to a $$\texttt{BST}$$. Write an iterative function that checks whether an element belongs to a $$\texttt{...
N-ary tree: A n-ary tree is a tree in which each node has at most $\texttt{n}$ children. The binary tree is a special case of n-ary tree in which n = 2. Given the following n-ary tree structure #define n ...typedef ... element;typedef struct node { e...
Binary search trees in levels: We would like in this question to arrange words of any length in a tree structure represented in levels as follows: each node $$p$$ of the tree of level $$i$$ has the following structure: typedef char element;typedef struct node{ element ...
Trees Traversal: Consider the following tree: **img**bsttraversals01.png##img## Give the inorder traversal of the above tree. Write a recursive function that prints the inorder traversal of a tree dynamically implemented. Write an iterative function that prints the...
Checking whether a tree is a BST by traversing it in inorder: The following function checks whether a given binary tree dynamically implemented is a BST or not. int isBST(Btree tree){ if(tree == NULL) return 1; if(tree->left != NULL && FindMax(tree->left) > tree->data) retur...
Generic Trees: A $$\texttt{Generic Tree}$$ can be represented as follows: **img**generictrees.png##img## The tree node declaration for general trees can be given as: typedef ... element; typedef struct node{ element data; struct node *firstChild; �...
Forest of Binary Search Trees: Consider a forest represented in the form of a linked list where each node points to a Binary Search Tree of words of length $$\texttt{L}$$. The list is sorted according to the length of the word. Example: After the insertion of the following words i...
Binary Search Tree of Events: A historian wants to classify a set of events. Each event is characterized by a $$\textit{title}$$, a $$\textit{location}$$ and a $$\textit{period}$$ of time (as most of the events are spread over several years). $$\textit{Title}$$ and $$\textit{loca...
Statically implemented Binary Tree: Write a recursive function $\texttt{int max$\_$rec(Btree B, int root$\_$index)}$ that returns the maximum element in a binary tree statically implemented rooted at index $\texttt{root$\_$index}$.Example: Consider the following Binary tree and its r...
Trace of MergeSort: Consider the following array: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 5 & 8 & 1 & 9& -2 & 10 & 3 & 2 & 6 & 2 & 0 & 7 & -4 \\\hline\end{array}$$ Trace MergeSort using the above table to sort ...
Spelling checker: (Session 2) In the proposed project during the year, you are asked to write a function that, given a string, returns the number of dictionary words with this string as a prefix (begins with that string). (Session 1) In the proposed project, answer...
Statically implemented Complete Binary Tree: A binary tree is called complete if all its non-leaf nodes have two children. Write a function that tests whether a binary tree statically implemented is complete....
Deepest element in a binary tree: Write a function $\texttt{deepest(A, E)}$ that returns the deepest level of the element E in the binary tree A or 0 if E $\notin$ A. We assume that the root of the tree is at level 1, and that the tree is dynamically implemented. Running example: ...
Binary tree rotations: In a binary tree (BT), a path between the root and a leaf is the number of arcs joining the root to the leaf. The BT $$\texttt{height}$$ is the length of the longest path between the root and each of the leaves. Write a function $$\texttt{int height(...
Modified BST: Consider the following declaration of a BST in which the field nbd denotes the number of descendants of a tree node: typedef struct node{ element data ; int nbd ; struct node *Left, *Right ;} *BST; Write a function that inserts...
Boolean expression: A Boolean expression is represented as a binary tree of strings (BT) in which internal nodes contain the logical connectors $$\texttt{AND}$$, $$\texttt{OR}$$ and $$\texttt{NOT}$$, and leaves contain strings representing Boolean variables. Ex: the ex...
Binary trees insertion: Write a recursive function to insert an element, passed as a parameter, into a binary tree. If the root is empty, the new entry should be inserted into the root, otherwise it should be inserted into the shorter of the two subtrees of the root (or int...
Printing a Binary tree: Write a function that will print all the elements from a binary tree in the bracketed form (data: LT, RT) where data is the element in the root, LT denotes the left subtree of the root printed in bracketed form, and RT denotes the right subtree in br...
Binary tree mirrors: Write a function that will interchange all left and right subtrees in a binary tree. **img**interchangebt.png##img##...
Common entries in two binary trees: Write a function that returns the number of common entries in two BTs....
Common entries in two binary search trees: Write a function that returns the number of common entries in two BSTs....
Merging two binary search trees: Write a function that merges 2 BST into a new BST....
Distinct values in a binary search tree: We consider a variant of BST where $\texttt{left(n)}$ $\leq$ $n$ $<$ $\texttt{right(n)}$ and this for any node $\texttt{n}$ in the tree. Write a function that calculates the number of distinct values in this kind of binary tree. Give the corre...
Delete common elements in two binary search trees: Given 2 BST $\texttt{A}$ and $\texttt{B}$, write a function that deletes from $\texttt{B}$ all the common elements with $\texttt{A}$....
Searching for an element in a Binary tree: Write a function for searching an element in a binary tree....
Half nodes in binary trees: Write a function that counts the number of half nodes (nodes with only one child) in the binary tree without using recursion....
Identical binary trees: Write a function that checks whether two binary trees are structurally identical....
Width of binary trees - recursive version: Write a function that computes the maximum width of a dynamically implemented BT. We define the maximum width of a BT as the maximum number of nodes located at the same level....
Binary tree mirrors check: Write a function that checks whether two binary trees are mirrors of each other **img**interchangebt1.png##img##...
Ancestors of a node in a Binary tree: Write a function that prints all the ancestors of a node in a Binary tree. For the tree below, and for 9 the ancestors are 9 2 6. **img**printbtree.png##img##...
Isomorphic binary trees: Write a function that checks whether tow binary trees are isomorphic. Two binary trees rare isomorphic if they have the same structure. The values of the nodes does not affect whether two trees are isomorphic or not. **img**isomorphic.png##img## **i...
Quasi-Isomorphic binary trees: Write a function that checks whether tow binary trees are quasi-isomorphic. Two binary trees rare isomorphic if they have the same structure. The values of the nodes does not affect whether two trees are isomorphic or not. Two binary trees B and C a...
Construction of k-ary tree: A full k –ary tree is a tree where each node has either 0 or k children. Given an array which contains the preorder traversal of full k–ary tree, write a function that construct the full k –ary tree. **img**narytree1.png##img##...
Ancestor sum in binary trees: A complete binary tree is a binary tree in which all level are completely filled: each non-leaf node has exactly 2 children and all leaves are located in the same level. Thus a tree of depth $n$ has 2$n$-1 nodes (1+2+4+8+$\cdots$). In this exercise, ...
Updating nodes in binary trees: Consider a binary tree of integers dynamically implemented; write a function update that changes node values such that each node is equal to the sum of its children. It is obvious that leaves remain unchanged. Example: **img**updatetree.png##img## ...
Nearest common ancestors in binary trees: Write a function that returns the value of the father of a given element in a binary tree of integers without repetition. Write a function that returns an array containing the values of all ancestors of a given element in a binary tree of integers wi...
Leftist binary trees: Consider a binary tree T. We define the path from the root to a leaf as the number of edges from the root to that leaf. The minimum path in a tree $T$ is the shortest path among all paths between the root and all leaves. Write a function $\texttt{int...
Static Binary Search Trees: A Binary Search Tree (BST) of whole integers can be represented by an array where the root is located at 0 and the contents of the remaining nodes correspond to the course in width of the tree. i.e. every node has two locations for its left and right...
Tracing QuickSort and Heapsort: Consider the following table: $$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline 9 & 15& 5 &7 &11 &4 &10 &13 &8\\\hline \end{array}$$ Trace $$\texttt{QuickSort}$$ using the above table to sort its entries. Trace $$\texttt{Heap...
Domain inclusion of heaps: A min-heap is a complete binary tree where the value of each element is less than the values of its children, if any. Remark: each value is unique in a heap (it can't be repeated). Define the data structure for dynamic implementation of a heap of i...
Kth smallest element in an array using QuickSort: Implement the following function $$\texttt{find_k}$$ : $$\texttt{int find_k(int A[], int N, int k);}$$ where $$\texttt{A}$$ is an array of distinct positive numbers, $$\texttt{N}$$ the dimension of the array, and $$\texttt{k} > 0$$. The function c...
Heap of prime factors: An integer number is represented by a heap consisting of the number prime factors. Ex: the number 24 is represented by the heap below: **img**heapprimefactors.png##img## Given the function $$\texttt{void primeFactors(int n)}$$ that prints the prime ...
Path with a given sum in binary trees: Write a function that checks whether a path with given sum exists in the tree. ...
Binary Search Trees Variant: We consider a variant of binary search trees in which $left(n) ≤ n < right(n)$ and this for any node $n$ of the tree. Given two binary search trees $A$ and $B$, we are interested in removing from the tree $B$ all the elements that are common to ...
Calkin-Wilf tree: The Calkin-Wilf tree is a complete binary tree. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction $\frac{a}{b}$ has as its two children the numbers $\frac{a}{a+b}$ and $\frac{a+b}{b}$. Every posit...
Stern-Brocot tree: The Stern-Brocot tree is an elegant construction to represent the set of all positive fractions. It was independently discovered by German mathematician Moritz Stern in 1858 and by French watchmaker Achille Brocot in 1861. The construction starts at ...

Back to the list of exercises

Select your ad blocker:

Disable AdBlock:

Disable AdBlock Plus:

Disable Adguard AdBlocker:

Disable uBlock Origin:

Recursion exercises in C Programming in C