Basic Recursion Problems

Here is a list of the most common basic recursion problems, along with a brief summary of each problem and links to examples in C with explanations for each of them.

Factorial Calculation

Problem: Compute the factorial of a non-negative integer n.
Summary: Calculate the product of all positive integers from 1 to n.

Fibonacci Sequence

Problem: Generate the nth term in the Fibonacci sequence.
Summary: Calculate the sum of the previous two terms to generate the next term in the sequence.

Exponentiation

Problem: Compute the result of raising a base number x to the power of an exponent n.
Summary: Multiply the base number by itself n times, using recursion.

Binary Search

Problem: Implement binary search to find a target element in a sorted array.
Summary: Divide the array in half and recursively search the left or right subarray, depending on the target's relationship to the middle element.

Sum of Array Elements

Problem: Find the sum of all elements in an array.
Summary: Add each element of the array to the sum, either directly or by recursively summing subarrays.

Greatest Common Divisor (GCD)

Problem: Calculate the greatest common divisor of two integers a and b.
Summary: Use Euclidean algorithm to repeatedly find the remainder of a divided by b and recursively call with new values.

Tower of Hanoi

Problem: Solve the Tower of Hanoi puzzle, moving n disks from one peg to another.
Summary: Move n-1 disks to an auxiliary peg, then move the largest disk, and finally move the n-1 disks to the destination peg.

Print Numbers

Problem: Print numbers from 1 to n in increasing or decreasing order.
Summary: Print a number, then recursively call to print the rest of the numbers.

Palindrome Check

Problem: Determine if a given string is a palindrome.
Summary: Compare the first and last characters of the string and recursively check the substring between them.

Binary Representation

Problem: Convert a decimal number to its binary representation. Summary: Divide the number by 2, keep track of remainders, and recursively call with the quotient.

Subset Generation

Problem: Generate all subsets of a set.
Summary: For each element, generate subsets that include and exclude it, recursively combining the results.

Permutations

Problem: Generate all permutations of a string.
Summary: Swap characters and recursively generate permutations for smaller substrings.

Count Digits

Problem: Count the number of digits in a positive integer.
Summary: Divide the number by 10, increment the count, and recursively call with the quotient until the number becomes 0.

Sum of Digits

Problem: Find the sum of the digits in a positive integer.
Summary: Extract the last digit, add it to the sum, and recursively call with the remaining digits until the number becomes 0.

Reverse String

Problem: Reverse a given string.
Summary: Swap the first and last characters, then recursively reverse the substring between them.

Greatest Element

Problem: Find the largest element in an array.
Summary: Compare each element with the maximum, updating it if a larger element is found, and recursively check the rest of the array.

Count Occurrences

Problem: Count the number of occurrences of a specific element in an array.
Summary: Check if the current element matches the target, increment the count, and recursively check the rest of the array.

Subset Sum

Problem: Determine if a subset of elements in an array sums up to a target value.
Summary: For each element, consider including or excluding it in the subset, and recursively check the remaining elements.

Binary Tree Traversal

Problem: Traverse a binary tree in preorder, inorder, or postorder. Summary: Visit the current node, recursively traverse the left subtree, then the right subtree (preorder); traverse left subtree, visit current node, then right subtree (inorder); traverse left subtree, right subtree, then visit current node (postorder).

These basic recursion problems provide a foundation for understanding and practicing recursive thinking. They cover a variety of concepts, from arithmetic calculations to searching and manipulation of data structures. By solving these problems, you'll develop a deeper understanding of recursion and its applications in problem-solving.

   Search this site: