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.