🎉 Yay! DSA-30 is now live!
Day 5 - Recursion
Basic Questions

Basic Questions

Sum of Natural Numbers

Code

Explanation

  1. Base case: n == 1
  2. Recursive case: n + sum(n - 1)

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Decimal to Binary COnversion

Code

Explanation

  1. Base case: n == 0
  2. Recursive case: decimalToBinnary(num / 2)
  3. Print the remainder of num / 2

Analysis

  • Time Complexity: O(log n)
  • Space Complexity: O(log n)

Modulo Operation

Code

Explanation

  1. Base case: num < den
  2. Recursive case: mod(num - den, den)
  3. Return num when num < den

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Find String Length

Code

Explanation

  1. Base case: str[0] == '\0'
  2. Recursive case: stringLength(str.substr(1))
  3. Return 1 when str[0] == '\0'

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Reverse a String

Code

Explanation

  1. Base case: str[0] == '\0'
  2. Recursive case: reverse(str.substr(1))
  3. Print str[0] when str[0] == '\0'

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Check if string is Palindrome

Code

Explanation

  1. Base case: start >= end
  2. Recursive case: isPalindrome(str, start + 1, end - 1)
  3. Return true when start >= end
  4. Return false when str[start] != str[end]

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Count Vowels in a String

Code

Explanation

  1. Base case: start >= end
  2. Recursive case: countVowels(str, start + 1, end)
  3. Return 0 when start >= end
  4. Return count + 1 when str[start] is a vowel

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Sum of numbers in a Singly Linked List

Code

Explanation

  1. Base case: head == NULL
  2. Recursive case: sumNodes(head->next)
  3. Return 0 when head == NULL
  4. Return head->data + sumNodes(head->next) when head != NULL

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Note: Once you have understood the above examples, try to solve the following problems on your own. (Using Recursion)

Extra Problems

  1. Print numbers from 1 to n
  1. Print numbers from n to 1
IntroductionProblem List