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

	/*
	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.
	3 > 10 > 5 > 16 > 8 > 4 > 2 > 1 = run length = 8
	*/
	public int getSteps(int n) {
	if(n == 1) {
	return 1;
	}
	return 1 + (n % 2 == 0) ? getSteps(n /2) : getSteps(3*n + 1);
	}

view raw FindCollapseSequence.cs hosted with ❤ by GitHub

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.