Recurrence, recursive function

Question

Type a number \$n\$. Then calculate \$f(n)\,ドル where

$$ f(n) = \begin{cases} n-10 & \text{if}~ n > 100\\[1.5ex] f(f(n + 11)) & \text{otherwise} \end{cases} $$

The output must show all the computations, such as $$f(99) = f(f(110)) = f(100) = f(f(111)) = f(101) = 91$$

Is there a shorter and better way I can solve this?

#include <iostream>
using namespace std;
int main(){
 int i=0, n, x, k;
cin>>n;
if(n>100) {
cout<<"f("<<n<<")=";
n=n-10;
}
else {
 cout<<"f("<<n<<")=";
while(n<=100){
loop: 
x=0;
k=0;
i++;
n+=11;
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")"; 
 }
 cout<<"="; 
 if(n>100){
 x=0;
 k=0;
 i=i-1;
 n=n-10;
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")";
 }cout<<"=";
 }
 if(n>100){
 x=0;
 k=0;
 i=i-1;
 n=n-10;
 if(i>=0){
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")";
 }cout<<"=";
 goto loop;
 }
 break;
 } 
 }
 }cout<<n;
 }

Answer 1

There's no way to tell this in a friendly manner: your indentation is abysmal.

Let's fix that up first. Note that there's plenty left to improve, like giving your operators some space, but I'll leave that as an exercise for yourself. Keep in mind space is cheap and readability is very important in code. If you can add readability by using some extra newlines or space, do it. But only if it helps. Don't throw them needlessly around just for the sake of it.

#include <iostream>
using namespace std;
int main(){
 int i=0, n, x, k;
 cin>>n;
 if(n>100) {
 cout<<"f("<<n<<")=";
 n=n-10;
 }
 else {
 cout<<"f("<<n<<")=";
 while(n<=100){
 loop: 
 x=0;
 k=0;
 i++;
 n+=11;
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")"; 
 }
 cout<<"="; 
 if(n>100){
 x=0;
 k=0;
 i=i-1;
 n=n-10;
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")";
 }
 cout<<"=";
 }
 if(n>100){
 x=0;
 k=0;
 i=i-1;
 n=n-10;
 if(i>=0){
 while(x<=i){ 
 x++;
 cout<<"f(";
 }
 cout<<n;
 while(k<=i){
 k++;
 cout<<")";
 }
 cout<<"=";
 goto loop;
 }
 break;
 } 
 }
 }
 cout<<n;
 }

Much better, but plenty left to improve.

Namespaces

using namespace std; is considered bad practice. Short code is not a requirement in C++, clear code is preferred. It's a thing commonly taught to new C++ programmers because it's 'easier', but it will royally bite you in the behind when conflicts arise.

goto

I'm not going to re-iterate how evil goto is, but please take a look at this well-written answer by 200_success. Basically, one should only use it in C++ if you know exactly what you're doing and there's no better alternative. There usually is a better alternative!

Be consistent!

x++ is usually reserved for for loops. Doing it in while loops indicates you're using the wrong tool for the job. You use x++, x += 1 and x = x + 1 or the negative version of it all over the place. There usually is no reason to write i = i -1, i -= 1 will do.

But the worst of it is:

Your code is simply incomprehensible. It takes too long to understand what it does and all the re-declaring of variables makes it hard to track what's going on. One-letter variables are usually not a good idea, iterators in for loops are an acceptable exception.

You have 6 while loops in your main function. 6!. I'd expect at least 3 different functions to keep this readable, with sensible returns passing the data along and there can't be a good reason to have this many while loops.

So?

Write down what you want to do as a flow-chart. Simplify it as much as possible. Implement that. The result will be half as complicated and twice as readable, at least. What you currently have is the result of a design flaw. I'm afraid a re-design, with this answer in the back of your head, is the only sensible solution here.

• A.LIE: Thanks! I removed the goto loop and two while loops. The condition is that i must not use functions, only loops and if else. I noticed that the second "if(n>100)" was useless. Again, Thanks for the advice.
• I'll add comments tomorrow: @A.L.I.E I hope you agree that "i must not use functions, only loops and if else." is information that you should have given in your question.
• A.LIE: Yes, but actually I was hoping for some "function" solutions, for the simple reason which is: I want to learn more about functions.
• Mast: @A.L.I.E Good! Functions are there for a reason, you definitely want to know a lot about them.

Answer 2

The core problem of the code (besides its horrible formatting, use of goto and using namespace std; that were addressed by others) is that it kind of half-unrolls the recursive/looping structure of the problem.

This is why you have the branching point twice. Look at all this duplicated code (indentation by me):

 if(n > 100)
 {
 x = 0;
 k = 0;
 i = i - 1;
 n = n - 10;
 if(n > 100)
 {
 x = 0;
 k = 0;
 i = i - 1;
 n = n - 10;

You should perform the if statement only once.

I suggest a different approach. Think about it like a stack. You have to keep track of 2 numbers:

1. the current number in the brackets (which start with whatever the input is)
2. the number of times the function f still has to be applied to it, which I call the stackHeight. (this always starts at 1)

All you have to do then is to manipulate these two numbers according to the formula you have.

#include <iostream>
using std::cout;
using std::cin;
using std::ostream;
using std::endl;
using std::string;
void streamMultipleTimes(ostream &out, string text, int amount)
{
 for (int n = 0; n < amount; n++)
 {
 out << text;
 }
}
int main()
{
 int n = 0, stackHeight = 1;
 cin >> n;
 while (stackHeight > 0)
 {
 streamMultipleTimes(cout, "f(", stackHeight);
 cout << n;
 streamMultipleTimes(cout, ")", stackHeight);
 cout << " = ";
 if (n > 100)
 {
 n -= 10;
 stackHeight -= 1;
 }
 else
 {
 n += 11;
 stackHeight += 1;
 }
 }
 cout << n << endl;
}

There you go. A little helper function to stream a text to an ostream a certain number of times. Other than that, there's not much to it.

Answer 3

I have no idea what x, k, and i represent. Frankly, I'm pleasantly surprised that the code works at all, since it is so complicated. As everyone else has already remarked, the formatting is atrocious — there is no way to sugar-coat that criticism.

You would probably be much better off implementing this recursive function using recursion.

#include <iostream>
int f(int n, std::ostream &out) {
 if (n > 100) {
 out << "f(" << n << ") = ";
 return n - 10;
 } else {
 out << "f(f(" << n << ")) = ";
 return f(f(n + 11, out), out);
 }
}
int main() {
 int n;
 std::cin >> n;
 std::cout << f(n, std::cout) << '\n';
}

Note that I've elected to pass an ostream explicitly as a parameter, to emphasize the fact that f is a function that has a side-effect of printing something.

Bonus

If you make the second parameter default to a no-op output stream, then you can call f(99) like a normal function that performs the calculation without tracing the calls.

class NullBuffer : public std::streambuf {
 public:
 int overflow(int c) { return c; }
};
static NullBuffer null_buf;
static std::ostream null_stream(&null_buf);
int f(int n, std::ostream &out=null_stream) {
 // Function body as above...
}

Answer 4

You can use two functions instead of one, one for calculating the value of f and other for printing all the intermediate steps!

 #include <iostream>
int f(int n); // to calculate the fnction f
void printFuncWithSteps(int n); // to print the function f with all its intermediate steps
int main()
{
 int n;
 while(std::cin >> n)
 {
 printFuncWithSteps(n);
 }
 return 0;
}
int f(int n)
{
 if(n > 100)
 {
 return n -10;
 }
 else
 {
 return f(f(n+11));
 }
}
void printFuncWithSteps(int n)
{
 std::cout << "f(" << n << ") = ";
 if(n>100)
 {
 std::cout << f(n) << " ";
 }
 else
 {
 int n1 = n+11;
 std::cout << "f(f(" << n+11 << ")) = ";
 printFuncWithSteps(f(n1));
 }
}

• 200_success: Please pick a consistent brace style. Also, never omit braces — the if-else in print_f() is awkward.
• Rishabh Agarwal: Edited to include the changes you specified!
• 200_success: The while still has a different brace style.
• Rishabh Agarwal: Can't loops/functions have different indentation than if/else statements? Is this a bad practice to do that?
• cat: @rishabhagarwal it's ugly.