Let the recursive function F(n) be defined as: 0, if n=1 F(n) = F(n/2), if n is

Question

Let the recursive function F(n) be defined as:

0, if n=1
F(n) = F(n/2), if n is an even (divisible by 2) positive number
F(3n+1), if n is an odd (non-divisible by 2) positive number

Write a C++ function that computes the number of transformation steps needed for a given positive number n to reach 0 via successive application of the function F.

For example, F(5) = F(16) (since 5 is odd, hence 3*5+1=16) = F(8) (since 16 is even, hence 16/2 = 8) = F(4) (similarly) = F(2) = F(1) = 0, which makes it a total of 6 transformation steps: 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 0.
You may assume (it can be proven mathematically) that 0 will be reached eventually, no matter what number you pick to start from.
Let the number n be supplied on the command-line , as a single argument to your code.

Thank You

Explanation / Answer

#include using namespace std; int transformations(int n,int count) { if(n==0) return count; else if(n==1) return transformations(0,++count); else if(n%2==0) return transformations(n/2,++count); else return transformations(3*n+1,++count); return 0; } int main() { int n; coutn; cout

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---