Why is recursion giving unexpected results

[IanB]

There is if the OP imagines that the println statement is [mysteriously] executed within the same sequence as the xMethod call, without xMethod being called first.

But no. The println(n) statement is inside the if (n > 0) block. Therefore it can never be executed when n = 0, regardless of whether xMethod is called before or after.

[kite31]

There is if the OP imagines that the println statement is [mysteriously] executed within the same sequence as the xMethod call, without xMethod being called first.

But no. The println(n) statement is inside the if (n > 0) block. Therefore it can never be executed when n = 0, regardless of whether xMethod is called before or after.

Obviously I know that.

I was trying to explain what the OP initially imagined might somehow be the case. We know 2+2 != 11

[golden_labels]

But, but… 2 + 2 = 11 (modulo 7)!

[kite31]

But, but… 2 + 2 = 11 (modulo 7)!

or base 3

[radiolistener]

or base 3

Indeed, since we are discussing programming, it seems only fair to appeal to one of the great guides of our discipline - Donald Ervin Knuth, the author of The Art of Computer Programming. Back in 1960, Knuth proposed a complex-base system whose radix is an imaginary or complex number.

If we take such a base \$xj\$, the seemingly absurd expression

\$2 + 2 = 11\$

can be written in positional notation as

\$2 \cdot (xj)^{0} + 2 \cdot (xj)^{0} \;=\; 1 \cdot (xj)^{1} + 1 \cdot (xj)^{0}\$

Solving this equation yields the complex solution \$x = −3j\$

Substituting back, the base becomes \$x \cdot j = -3 \cdot j^{2} = 3\$

So, after detouring through Knuth’s imaginary number system, we come full circle: the notorious identity 2+2=11 turns out to be perfectly valid - in base 3.

After all, in mathematics as in programming, changing the base is often the quickest way to make impossible things compile. And our brief detour into complex numbers just shows - when 2 + 2 looks impossible, just add a little imaginary help...

[magic]

It's kindergarten maths to show that this can (only) work in base 3:

2 + 2 = 1·x + 1

It would take three digits to make things complex:

2 + 2 = 129
2 + 2 = x² + 2x + 9
-4 = (x + 1)²
2i = ±(x + 1)
x = -1 ± 2i

[TheCalligrapher]

So, after detouring through Knuth’s imaginary number system, we come full circle: the notorious identity 2+2=11 turns out to be perfectly valid - in base 3.

It is indeed. However, the problem often is that some people take this as a demonstration of "two plus two equals four" not always being valid. They mistakenly believe that the above somehow demonstrates that "two plus two can be eleven". Such people fail to grasp the difference between notational systems for numbers and numbers themselves. They fail to understand that "11" in base 3 is actually four, not eleven. So, the whole "2+2=11" in base 3 just reiterates the good old "two plus two equals four".

[radiolistener]

They mistakenly believe that the above somehow demonstrates that "two plus two can be eleven".

There is no mistake at all. In base-3, 2 + 2 = 11 is absolutely valid — it only looks odd if you insist on reading it with base-10 goggles.

A number is a single abstract entity, the digits we use in a given base are just a language to express that entity. You can represent the same thing with different digit sequences in different numeral systems, just like you can express the same thing meaning with different words in different languages. All of them are valid — they’re simply express exactly the same thing using different languages.

They fail to understand that "11" in base 3 is actually four, not eleven.

I understand what you wanted to say, but your phrase "11 in base 3 is actually four, not eleven" sounds a bit off, because in base 3 there is no such thing as "4". Numbers there stop at 2 — poor 3 and 4 never get invited to the party! 

What you probably mean to say is that "11" in base-3 represents the same quantity that we normally write as “4” in base-10. Without that clarification, some readers may get confused.

So, the whole "2+2=11" in base 3 just reiterates the good old "two plus two equals four".

Exactly — the equation is still true, just wearing a different base-system outfit. Same truth, different costume

[magic]

Such people fail to grasp the difference between notational systems for numbers and numbers themselves.

[wilfred]

I understand what you wanted to say, but your phrase "11 in base 3 is actually four, not eleven" sounds a bit off, because in base 3 there is no such thing as "4". Numbers there stop at 2 — poor 3 and 4 never get invited to the party! 

11₃ is 1 x 3¹ + 1 x 3⁰ or 3 + 1 which equals 4. Just because there is no digit 4 used to write down the numbers in base 3 doesn't mean you can't count to 4 or represent the number 4.

[radiolistener]

11₃ is 1 x 3¹ + 1 x 3⁰ or 3 + 1 which equals 4.

I understand your point, but if your expression is written in base-3, there is no digit “4” in that system, so using it directly would be invalid.

What you probably meant is that “11” in base-3 corresponds to 4 in base-10. If you want to express it this way, you need to explicitly specify that the 4 is written in a different base than the one used by default in the expression. Otherwise, it can easily lead to confusion.

In other words, writing "11 equals 4" is incorrect - this is mistake, whereas writing "11₃ equals 4₁₀" is correct and perfectly valid.

When working with an expression in base-N, it is generally expected that all numbers are interpreted in base-N by default. You cannot introduce digits or numbers from another base without explicitly indicating their base.

It’s similar to writing a text in English: you cannot just drop random words in Chinese without explanation — readers won’t understand them. In the same way, if an equation is written in base-3, you cannot suddenly use a digit like “4” without explicitly specifying its base.


While this may seem obvious to some, and those who understand your intent might infer it even if you ignore the rule, it is nonetheless a serious mistake to mix digits from different numeral systems in a single text or equation without explicitly specifying their bases.

You may choose any numeral system as the default without explicitly specifying its base, as long as all numbers in your text or equation are consistently expressed in that system — for example, using base-3 throughout is perfectly fine. However, you cannot mix numbers from different numeral systems without explicitly indicating their bases.

[Nominal Animal]

Thank you all I seem to have get it.

If you want to explore more complex recursion systems, for example what calls are made and in what order when calculating a specific value in the Fibonacci series, I would recommend you add another tool to your arsenal: Graphviz.  It is a set of programs that take textual descriptions of graphs and nets in the human-readable DOT language, and draws the graph/net as an image, automatically placing nodes and edges according to tool-specific rules.  dot draws standard directed and undirected graphs and nets, circo places nodes in a circle, and so on.

Each node does require an unique identifier, which can be text, number, or even a pointer (using format \"%p\").  I recommend using a variable and a getter function to obtain a new unique id:

Code: [Select]

static int  unique_ids = 0;

static inline int  unique_id(void) {
    return ++unique_id;
}
which simply increments the unique_ids variable and returns the incremented value.

A program that calculates say the 6th number in the Fibonacci series printing the call graph would be

Code: [Select]

#include <stdlib.h>
#include <stdio.h>

static int  unique_ids = 0;

static inline int  unique_id(void) {
    return ++unique_ids;
}

int fibonacci(FILE *dot, int n, int caller_id) {

    /* Grab a new unique ID, identifying this particular call in the DOT graph */
    int  id = unique_id();

    /* 'result' will eventually specify the calculated n'th Fibonacci number, F(n). */
    int  result;

    /* F(n) = F(n-1) + F(n-2), but F(0) = 0, F(1) = 1. */
    if (n < 2) {
        result = n;
    } else {
        result = fibonacci(dot, n-1, id) + fibonacci(dot, n-2, id);
    }

    /* Describe this node in DOT, if 'dot' is non-NULL */
    if (dot) {
        /* First, describe this node */
        fprintf(dot, "    \"%d\" [ label=\"F(%d) = %d\" ];\n", id, n, result);
        /* Then describe the edge to the parent (who called this function) */
        fprintf(dot, "    \"%d\" -> \"%d\";\n", id, caller_id);
    }

    /* As usual, this function returns the calculated n'th Fibonacci number. */
    return result;
}

int main(void) {

    /* Standard output consists of a directed graph in DOT language: */
    fprintf(stdout, "digraph {\n");

    /* Zero ID is the following fibonacci(stdout, 6, 0); call */
    int  result = fibonacci(stdout, 6, 0);
    fprintf(stdout, "    \"0\" [ label=\"fibonacci(stdout, 6, 0) = %d\" ];\n", result);

    /* End of directed graph. */
    fprintf(stdout, "}\n");

    /* We also print the result to standard error. */
    fprintf(stderr, "fibonacci(6) = %d, used %d recursive calls\n", result, unique_ids);

    return EXIT_SUCCESS;
}
To standard error, this outputs
    fibonacci(6) = 8, used 25 recursive calls
and to standard output, the following DOT language directed graph:

Code: [Select]

digraph {
    "6" [ label="F(1) = 1" ];
    "6" -> "5";
    "7" [ label="F(0) = 0" ];
    "7" -> "5";
    "5" [ label="F(2) = 1" ];
    "5" -> "4";
    "8" [ label="F(1) = 1" ];
    "8" -> "4";
    "4" [ label="F(3) = 2" ];
    "4" -> "3";
    "10" [ label="F(1) = 1" ];
    "10" -> "9";
    "11" [ label="F(0) = 0" ];
    "11" -> "9";
    "9" [ label="F(2) = 1" ];
    "9" -> "3";
    "3" [ label="F(4) = 3" ];
    "3" -> "2";
    "14" [ label="F(1) = 1" ];
    "14" -> "13";
    "15" [ label="F(0) = 0" ];
    "15" -> "13";
    "13" [ label="F(2) = 1" ];
    "13" -> "12";
    "16" [ label="F(1) = 1" ];
    "16" -> "12";
    "12" [ label="F(3) = 2" ];
    "12" -> "2";
    "2" [ label="F(5) = 5" ];
    "2" -> "1";
    "20" [ label="F(1) = 1" ];
    "20" -> "19";
    "21" [ label="F(0) = 0" ];
    "21" -> "19";
    "19" [ label="F(2) = 1" ];
    "19" -> "18";
    "22" [ label="F(1) = 1" ];
    "22" -> "18";
    "18" [ label="F(3) = 2" ];
    "18" -> "17";
    "24" [ label="F(1) = 1" ];
    "24" -> "23";
    "25" [ label="F(0) = 0" ];
    "25" -> "23";
    "23" [ label="F(2) = 1" ];
    "23" -> "17";
    "17" [ label="F(4) = 3" ];
    "17" -> "1";
    "1" [ label="F(6) = 8" ];
    "1" -> "0";
    "0" [ label="fibonacci(stdout, 6, 0) = 8" ];
}
If you pipe the output to dot, or save it to a file and run dot specifying the name of that file, you will see the graph itself,

^{(Click to embiggen)}

I personally have over three decades of paid software development in various programming languages, including a lot of C.  Yet, I still prefer to use tools like Graphviz to verify my understanding of algorithms and even complex data structures (and how they refer to each other).  Thus, I would suggest that learning how to augment your learning programs with DOT language output can help you produce better code, because you then understand the code better (as in how it works, how it computes the results, how many calls are needed, and how to make it much more efficient).  For example, the above call graph shows that many Fibonacci numbers are calculated again and again, so caching the already calculated results would make it much faster.  In reality, there are better mathematical forms to use than the basic sum formula (Binet's formula being most powerful, but requiring arbitrary-precision numbers for larger n), but I'm sure you see the usefulness of such graphs.

(I personally only use Linux for development.  Development on Macs is very similar, but on Windows, there are quirks and exceptions, even when using WSL2.  Because I do not know what operating system you use (or anyone else reading this post uses), I omitted the exact commands you use, because Graphviz is available for free and works in all operating systems.  Whenever there is a graphical desktop available, it can display the graph directly, but it can also just generate the image file instead.  Thus, this development pattern will work on any operating system, and even with any programming language.  I've found it extremely powerful, and hope you find it useful too.)

An even more important thing, in my opinion, is writing useful comments.  The comments should never describe what the code does, because we can read that from the code itself.  The comments should always try to convey your intent and reasoning instead, so that those reading the code can compare what the comment says about the intent for the code and what the code actually does.  I did not learn this early enough, and still have trouble writing the kind of comments I would like to, so the earlier you learn to do this, and always write such comments, the better a programmer you will become.  I am literally limited by this, because the maintainability of the code I write suffers due to my comments not being as useful and to the point they could be!  I hope you become better than I am, eventually.

[IanB]

I understand what you wanted to say, but your phrase "11 in base 3 is actually four, not eleven" sounds a bit off, because in base 3 there is no such thing as "4".

Don't be silly. Of course the number four exists when you are counting in base 3 or in any base. You can visualize it: start with the number one, and then find its successor three times. The third successor of one is the quantity four. Just as "IV" is also the quantity four.

(Note that TheCalligrapher didn't write the digit "4", they said the number "four". There is a difference.)

This is just the same as "a dozen", or "a score" or "a gross" exist independently of notational systems. If I am counting in base 10 and you are counting in base 2, and I ask you for a gross of pencils, I will (hopefully) get the right number of pencils. Named quantities exist, regardless of the notational system in use to write them down.

[radiolistener]

Don't be silly. Of course the number four exists when you are counting in base 3 or in any base.

Sorry for being pedantic, but the number “four” does not exist if you are counting in base‑3. I understand that you meant “four in base‑10”, but the way it was written initially is mistaken. In base‑3, there is no concept of “four” or the digit “4”.

You can visualize it: start with the number one, and then find its successor three times. The third successor of one is the quantity four. Just as "IV" is also the quantity four.

(Note that TheCalligrapher didn't write the digit "4", they said the number "four". There is a difference.)

This is just the same as "a dozen", or "a score" or "a gross" exist independently of notational systems. If I am counting in base 10 and you are counting in base 2, and I ask you for a gross of pencils, I will (hopefully) get the right number of pencils. Named quantities exist, regardless of the notational system in use to write them down.

I understand the distinction you are making between abstract numbers and their representation. However, the problem here is one of consistency in notation.

When specifying the value of an abstract number, you must use a particular numeral system. Since base‑3 is the default in the context, you cannot use “four” without indicating its base, because by default only numerals valid in base‑3 may be used. However, if you explicitly indicate that “four” is in base‑10, then the statement becomes correct.

In the context where base‑3 is the default, “11” is the valid numeral. Writing “11 = 4” is misleading because it mixes numeral systems without explicitly specifying the base. The correct way to express the equivalence is 11₃ = 4₁₀, which clearly separates the abstract quantity from the symbols used to represent it.

The core mistake in TheCalligrapher’s statement is assuming that base‑10 digits can be inserted into a base‑3 context without clarification. Since base‑3 contains no digit “4” using it in that context is invalid — even abstractly — unless the base is explicitly indicated.

I made corrections for the TheCalligrapher quote: "eleven in base 3 is actually four in base 10, not eleven in base 10". With these corrections it will be correct. But this is not what TheCalligrapher wrote originally. And this is what I'm talking about.


This is analogous to reporting measurements in meters and inches without specifying units. Or it is similar to comparing values in dBW and dBV while labeling both simply as dB. Using a consistent default is fine, but mixing units (or bases, or reference level) without clarification is misleading.

In short: once a default base is established, all numerals must be interpreted within that base, or any deviation must be explicitly marked. Treating “4” as if it were valid in a base‑3 expression is simply incorrect. Even if you mean that "4" is in base‑10, if it is not explicitly marked, it is still incorrect in base-3 context.

PS: The original humor in the statement that 2 + 2 = 11 is valid in base‑3 relies on the fact that the expression was written using a default numeral system, while the default system itself was not explicitly specified, leaving the choice of an appropriate default base to the reader. Using base‑3 as the default — just as one could use base‑10 or any other base — is perfectly acceptable. However, mixing values from different numeral systems without explicitly indicating their bases is incorrect.


Often, the intended meaning can be inferred from context, for example, when someone writes “mHz”, it is frequently understood that he mean “MHz”. Similarly, in this case, the intended reference to “4” within a base‑3 context is generally understandable. Nevertheless, it remains an error that should be avoided, as it can create confusion, and such mistakes are not always easily resolved from context alone.

Sorry for being so pedantic, but the statement about “4” in a base‑3 context caught my eye, which is why I commented it. I did not expect it to provoke such a strong reaction, as I thought these issues should be fairly straightforward and not confusing.

[IanB]

Sorry for being pedantic, but the number “four” does not exist if you are counting in base‑3. I understand that you meant “four in base‑10”, but the way it was written initially is mistaken. In base‑3, there is no concept of “four” or the digit “4”.

No, I did not mean "four in base-10", I meant "four" as in the word found in the dictionary--meaning the number that comes after the number that comes after the number that comes after one. There are four fingers on your hand, and that is true whether you choose to write that number down in base 2, in base 16, or in French. It is always the same number of fingers.

When specifying the value of an abstract number, you must use a particular numeral system.

Why? Can you provide a justification for that? How did people count before there were Arabic numerals or complex notation systems? How did people count when they used tally marks? Four is four is four. It is a quantity everyone knows and can relate to. It can be expressed in different number systems, but the word four is universal in its meaning. It is what you get to when you count with the natural numbers: one, two, three, four.

In the context where base‑3 is the default, “11” is the valid numeral. Writing “11 = 4” is misleading because it mixes numeral systems without explicitly specifying the base.

That may be so, but nobody is writing that, so you are constructing a straw-man argument.

The core mistake in TheCalligrapher’s statement is assuming that base‑10 digits can be inserted into a base‑3 context without clarification.

But TheCalligrapher did not do that, so once again you are creating a straw man argument.

Sorry for being so pedantic, but the statement about “4” in a base‑3 context caught my eye, which is why I commented it. I did not expect it to provoke such a strong reaction, as I thought these issues should be fairly straightforward and not confusing.

Once again, there was no "4" in a base 3 context. You are inventing it.

Please stop responding to what you think you might have read, and instead try responding to what is actually written. You will do much better then.

[radiolistener]

No, I did not mean "four in base-10", I meant "four" as in the word found in the dictionary--meaning the number that comes after the number that comes after the number that comes after one. There are four fingers on your hand, and that is true whether you choose to write that number down in base 2, in base 16, or in French. It is always the same number of fingers.

I understand your point, but whether you intend it or not, the symbol “4” is not the abstract quantity itself but rather its representation in the numeral system with base-10. The quantity — the concept, such as the number of fingers on a hand, is indeed independent of language or numeral system. However, not all culture expressing it using base-10 and once you write it down as "4", you are already expressing it in base-10 notation.

I understand your point that when people say “four”, they intuitively think of a certain quantity. However, the mistake is to conflate that intuitive notion with the numeral system used to represent it. The word “four” or the digit “4” specifically expresses that quantity in base‑10 notation. It is not the abstract quantity itself. Please don't confuse it.

Why? Can you provide a justification for that? How did people count before there were Arabic numerals or complex notation systems? How did people count when they used tally marks? Four is four is four. It is a quantity everyone knows and can relate to. It can be expressed in different number systems, but the word four is universal in its meaning. It is what you get to when you count with the natural numbers: one, two, three, four.

You are correct that the abstract quantity itself exists independently of any numeral system or language. However, the symbols "4" or “four” are not the abstract quantity, they are a representation of that quantity in base‑10. In other languages, or using other numeral systems, the same abstract quantity would be expressed differently — for example, in Chinese, the same quantity is written as "四" in base‑10.

But when working within a numeral system with a fixed base, consistency is required. You can really omit explicitly stating the base if a default is established — for example, base‑10 is commonly assumed. However, if an expression is written in a context where base‑3 is the default, you cannot introduce a numeral from another system without explicitly specifying its base. Mixing values from different numeral systems without such clarification is misleading and incorrect.

For example, with default base-10:
- stating "11 = 4" is incorrect
- stating "11₃ = 4" is correct
- stating "11 = 4₁₀" is incorrect
- stating "11₃ = 4₁₀" is correct

But with default base-3, it's a little bit different:
- stating "11 = 4" is incorrect
- stating "11₃ = 4" is incorrect  (this is the case we're talking about)
- stating "11 = 4₁₀" is correct
- stating "11₃ = 4₁₀" is correct

In the context where base‑3 is the default, “11” is the valid numeral. Writing “11 = 4” is misleading because it mixes numeral systems without explicitly specifying the base.

That may be so, but nobody is writing that, so you are constructing a straw-man argument.

The core mistake in TheCalligrapher’s statement is assuming that base‑10 digits can be inserted into a base‑3 context without clarification.

But TheCalligrapher did not do that, so once again you are creating a straw man argument.

Sorry for being so pedantic, but the statement about “4” in a base‑3 context caught my eye, which is why I commented it. I did not expect it to provoke such a strong reaction, as I thought these issues should be fairly straightforward and not confusing.

Once again, there was no "4" in a base 3 context. You are inventing it.

I understand your point, but from your statements it seems you are treating TheCalligrapher’s comment as if it were in a base‑10 context. However, the original expression 2 + 2 = 11 was clearly in a base‑3 context, and TheCalligrapher did not explicitly switch the base to 10. Therefore, this is not a straw man argument — it’s a typical mistake of introducing values from one context to another without explicit clarification. It’s like discussing lengths in meters and suddenly quoting a number in inches without stating the unit — that would be clearly incorrect.

Please stop responding to what you think you might have read, and instead try responding to what is actually written. You will do much better then.

I am not responding to "what I think you might have read”. The context under discussion is the expression 2 + 2 = 11, written in using default base‑3 and explicitly defined that it written with default base-3. In that context, using the numeral “4” without specifying its base is a genuine error. It may appear obvious from context that he intended it to represent a number from a different numeral system, but the fact remains: introducing a value from another base without explicit notation is incorrect. This is not a matter of interpretation or imagination—it is a concrete issue of mixing numeral systems without clarification.

For me, it is entirely obvious, that the base‑10 is not the absolute standard. I find it strange to read arguments suggesting that, because humans have ten fingers, everyone should automatically interpret any numerals with no explicit base in base‑10 only. This is simply not correct. When responding to an expression written with base‑3 as the default, one must either adhere to that base-3 notation or explicitly switch the context by indicating that the numerals in his answer are being expressed in a different base by default.

It appears that some people really have difficulty distinguishing between a numeral written in base‑10 and the abstract quantity it represents, often conflating the two and assuming that a base‑10 representation is absolute. I find its hard to understand why so simple thing is still not understand, but I have at least made an effort to explain it.

Sorry for being so pedantic. I understand that many people do not notice differences in context and may mix numbers across different units, numeral systems, reference points, or, for example, write “mHz” instead of “MHz” without seeing any issue. For some, pointing out such the mistake makes little difference, as they simply do not perceive it as a problem. However, I consider this to be a significant mistake.

[radiolistener]

As I mentioned earlier, if TheCalligrapher had initially properly specified the base for the numerals 4 and 11, there would have been no reason for this discussion at all. In fact, the substance of his message essentially boils down to stating the obvious thing — like saying “cotton is fluffy” or “sugar is sweet”, since it should already be clear to everyone that 4₁₀ and 11₁₀ are different numbers, while 4₁₀ and 11₃ represent the same number.

And isn’t it striking how simple and transparent everything becomes once the bases are properly indicated? It immediately clarifies that “4” does not belong to the base-3 context in which it was inserted, and removes any confusion about why he claimed that 11 is 4 but not 11.

However, I was somewhat surprised by the discussion, as it revealed that some people genuinely believe a number is always expressed in base-10. This is a rather puzzling misconception. In fact, the term number refers to the underlying abstract entity — the quantity, and applies equally regardless of the numeral system used to represent it.

There is nothing wrong to say something like hexadecimal number, decimal number, binary number, etc.