Recursion

- Fundamentals -

Factorial Calculator

1. Design an algorithm that calculates the factorial of a given non-negative integer 'n'.

  • Parameters - (N)
  • Output - Integer as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String n = 0 n = large positive integer (e.g., 15) n = 1
Output 1 1307674368000 (15!) 1
Explanation The base case: factorial(0) = 1, minimal computation, immediate return. Maximum number of recursive calls and multiplications, function recursively called n times. Very minimal recursion, factorial(1) = 1 × factorial(0), quick return after two calls.

Nth Fibonacci Term

2. Design an algorithm that returns the Nth term of the Fibonacci sequence.

  • Parameters - (N)
  • Output - Integer as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String n = 0 n = large positive integer (e.g., 20) n = 1
Output 06765 (20th Fibonacci number) 1
Explanation Base case: n = 0, function directly returns 0 with no recursion. Requires maximum recursive calls, exponential time complexity O(2^n), recalculating subproblems repeatedly. Base case: n = 1, function directly returns 1 quickly without further recursion.

String Reversal

3. Design an algorithm that returns the reverse of a string.

  • Parameters - (String)
  • Output - String as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String "a" (single character string) "abcdefghijklmnopqrstuvwxyz" (long string) "" (empty string)
Output "a" "zyxwvutsrqponmlkjihgfedcba" ""
Explanation Base case: string of length 1, recursion stops immediately. No need to rearrange. Maximum recursion depth required, string length n. Each recursive call processes one character. Base case: empty string, recursion stops immediately. Direct return of empty string.

Check Palindrome

4. Design an algorithm that return 1 if the string is a palindrome else return 0.

  • Parameters - (String)
  • Output - 1 or 0 as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String "a" (single character string) "abcdefghhgfedcba" (long palindrome string) "" (empty string)
Output 111
Explanation String of length 1 is always a palindrome. Comparison stops immediately. Requires full comparison of all characters (O(n/2) comparisons), especially if string is palindrome. Empty string is trivially a palindrome by definition. Immediate return of 1.

Digits Sum

5. Design an algorithm that returns the sum of all digits of a given positive number 'n'.

  • parameters - (integer n)
  • output - calculation as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String 5 (single-digit positive integer) 999999 (large multi-digit integer with all 9's) 0 (zero as input)
Output 5 54 0
Explanation Single-digit input, returns immediately without recursion. Maximum recursion depth as the number has many digits. Each digit (9) contributes to the sum. Zero is considered a valid edge case. Sum of digits = 0. Base case returns immediately.

Search in Array

6. Design an algorithm that return the index of target element in an integer array.

If no such element found in the array the algo should return '-1'.

  • Parameters - (integer array), (target integer)
  • Output - index as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String Array: [5, 3, 8, 2] Target: 5Array: [1, 2, 3, 4, 5] Target: 10Array: [] Target: 5
Output 0 (First index match) -1 (Target not present) -1 (Empty array case)
Explanation Target found at first index, loop exits early. Full traversal required; target not found. Empty array, immediately return -1.

- Intermediate Problems -

All Possible Subsets

1. Design an algorithm that generates all unique lexicographically sorted subsets (without repetition) from a data array of N integers( with possible duplicates ).

  • Parameters - (Array)
  • Output - Subsets as per above problem statement.
Parameter \ Case Best Case Worst Case Edge Case
Input String Array: [1, 2, 3] Array: [1, 1, 1, 1, 1] (All Duplicates) Array: [] (Empty Array)
Output [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] [[], [1], [1,1], [1,1,1], [1,1,1,1], [1,1,1,1,1]] [[]]
Explanation Small distinct elements, minimal duplicates, sorted naturally All elements same, maximum redundant subsets, algorithm skips carefully No elements, only empty subset returned

String Permutation

2. Design an algorithm that generates all lexicographically sorted permutations of a string.

  • Parameters - (String)
  • Output - Sorted Output as per above problem statement.
Parameter \ Case Best Case Worst Case Edge Case
Input String "ab" "abcdef" (6 unique characters) Empty string "" or single character string
Output ["ab", "ba"] ["abcdef", ..., "fedcba"] (720 permutations) [] or [ "a" ]
Explanation Only 2 characters ⇒ 2 permutations, trivially sorted 6 characters ⇒ 6! = 720 permutations to generate and sort No permutations possible for empty string or trivial single char

Power Function

3. Design an algorithm that computes 'x' raised to the power of 'n', where x is a floating-point number and n is an integer (can be positive, negative, or Zero).

  • x is a floating-point number (-10^3 ≤ x ≤ 10^3)
  • n is an integer (-10^5 ≤ n ≤ 10^5) and can be positive, negative, or zero

Return the Floating-point result rounded to 6 decimal places.

  • parameters - (floating-point 'x'), (integer 'n')
  • output - computation as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String x = 5.0, n = 0x = 2.0, n = 100000 x = 0.0, n = 0 or x = 0.0, n = -5
Output 1.000000 Very large number (1.071508e+301 approx) 1.000000 or undefined (zero base, negative exponent)
Explanation Any number to power 0 is 1 Requires max recursive/iterative steps to compute Handling zero base with zero/negative exponent carefully to avoid division by zero or indeterminate forms

Preorder Traversal

4. Given a binary tree represented as a flat array in level-order traversal, Design an algorithm that returns the preorder traversal (Root -> Left -> Right) of the binary tree.

  • Parameters - (Flat Array Level Order Traversal of the binary tree)
  • Output - Pre order traversal of the binary tree.
Parameter \ Case Best Case Worst Case Edge Case
Input String [1] (Single node tree) Complete tree of height h with no nulls [ ] (Empty array) or tree with all nulls
Output [1] Full preorder traversal of all nodes [] (Empty list)
Explanation Minimal tree, immediate return after visiting root Visits all n nodes → deepest possible recursive calls (up to O(n) time) No valid nodes to process, returns empty result

Inorder Traversal

5. Design an algorithm that return the ( Left -> Root -> Right ) inorder traversal of a binary tree.

Binary tree as input is represented in the form of flat Array level order traversal.

  • Parameters - (Flat Array Level Order Traversal of the binary tree)
  • Output - In order traversal of the binary tree.
Parameter \ Case Best Case Worst Case Edge Case
Input String [1] (Single node tree) Complete tree of height h with no nulls [ ] (Empty array) or tree with all nulls
Output [1] Full preorder traversal of all nodes [] (Empty list)
Explanation Minimal tree, immediate return after visiting root Visits all n nodes → deepest possible recursive calls (up to O(n) time) No valid nodes to process, returns empty result

Postorder Traversal

6. Design an algorithm that return the ( Left -> Right -> Root ) Postorder traversal of a binary tree.

Binary tree as input is represented in the form of flat Array level order traversal.

  • Parameters - (Flat Array Level Order Traversal of the binary tree)
  • Output - Postorder traversal of the binary tree.
Parameter \ Case Best Case Worst Case Edge Case
Input String [1] (Single node tree) Full binary tree [1, 2, 3, 4, 5, 6, 7] Empty array [] or array like [null, null, null]
Output [1] [4, 5, 2, 6, 7, 3, 1] [] (Empty list)
Explanation Minimal tree, immediate return after visiting root Visits all nodes recursively, depth-wise No valid nodes, directly returns empty result

Binary Tree Paths

7. Design an algorithm that returns all possible paths from the root node to each leaf node.

Each path should be in a sequence of node values from the root to the leaf. The paths should be seperated by arrows ( -> )

  • Parameters - (Flat Array Level Order Traversal of the binary tree)
  • Output - Paths according to above problem statement.
Parameter \ Case Best Case Worst Case Edge Case
Input String [1] [1,2,3,4,5,6,7] [] or [null, null, null]
Output ["1"] ["1->2->4", "1->2->5", "1->3->6", "1->3->7"] []
Explanation Single root node path Visits all nodes, generates all leaf paths No valid nodes, no paths to return