Recursive function question

March 1, 2018

Introduction

I like to find some algorithm easy to solve and use it as the first mock interview algorithm. 

The link is here. 

Problem statement:

f(n) = 3n + 1 if n is odd or n/2 if n is even. Collapse sequence refers to each number according to this formula until the sequence becomes equal to 1. Find the number ( which is not greater than 10000), which will have the longest Collapse sequence. 

      

For example:

3 > 10 > 5 > 16 > 8 > 4 > 2 > 1 = run length = 8

Problem solving

The ideal case is to go over the example n = 3, and then follow the definition of the function, find out that each intermediate steps like the following: 3 > 10 > 5 > 16 > 8 > 4 > 2 > 1, run length = 8.

The next step is to write the calculation using recursive function. The first step to go over n = 3 takes 5 minutes, writing the recursive function takes another 5 minutes.