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.

Advertise on this site. I promise you will like the rates :)

Problem: Compute the factorial of a non-negative integer n.

Summary: Calculate the product of all positive integers from 1 to n.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Problem: Generate all subsets of a set.

Summary: For each element, generate subsets that include and exclude it, recursively combining the results.

Problem: Generate all permutations of a string.

Summary: Swap characters and recursively generate permutations for smaller substrings.

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.

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.

Problem: Reverse a given string.

Summary: Swap the first and last characters, then recursively reverse the substring between them.

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.

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.

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.

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: