RECUR29 - Editorial

editorial
,
1

Problem Link - Collatz Conjecture in Recursion

Problem Statement:

You are required to write a recursive function to implement the Collatz conjecture (also known as the 3n + 1 problem). The Collatz conjecture is a mathematical sequence defined as follows:
Start with any positive integer n.

  • If n is even, divide it by 2.
  • If n is odd, multiply it by 3 and add 1.

Repeat the process with the resulting number until it becomes 1.
The conjecture suggests that no matter what value of n you start with, you will always eventually reach 1. Return the number of steps it takes for n to become 1.

Approach:

  • Base Case: If N=1, return 0, because no steps are required.
  • Recursive calls: Depending on whether N is even or odd, apply the respective rule and recursively calculate the number of steps for the next number.

Complexity:

  • Time Complexity: The time complexity is O(log n) on average, but in the worst case (when n is odd and requires more multiplications), it could be higher for certain numbers.
  • Space Complexity: The space complexity is O(log n) due to the recursion stack depth.