Recursion on Recursion in C

Question

I have a hard time understanding the part of the code where the program is recalling on the recursion multiple times.

The output is 1233333. If I change the recursion line to just fun (++count;). the output is 123, which I understand the logic, but when you start calling on the recursion multiple times, I become lost.

#include <stdio.h> 
int fun(int count) { 
    printf("%d\n", count);
    if(count < 3) { 
        fun(fun(fun(++count)));
    }
    return count;
}

int main() 
{ 
    fun(1);
    return 0; 
}

The function stops recursing when it receives greater than 2. That's why it just kept printing 3 after 1 and 2 because count is no longer getting incremented past 3. Note the the very first recursion is done 3 times deep. — alvits, Nov 13 '15 at 03:58
@alvits If the first recursion is being replicated three times wouldn’t the output be 111? — L.Jastrem, Nov 13 '15 at 05:56
No. ++count is pre increment therefore the deepest call will be fun(2). This will then enter fun() and print 2 and will call fun(++count) again which will be fun(3). When it enters fun(), it will not call fun() anymore cause it's no longer less than 3. And from here on the deepest called fun() will return as parameter to fun(), which is 3. When returning back to caller, the value of count is no longer getting printed becuase the printf was called prior to recursion. — alvits, Nov 13 '15 at 06:02
The fun(fun(fun(++count))) will be like fun(fun(fun(2))) which will become fun(fun(3)) on return of the deepest. Then it will become fun(3) when the previous one returns. — alvits, Nov 13 '15 at 06:09
It fills no purpose to understand code like this. All you need to learn is to recognize that it is bad and that you should avoid recursion in general, because it is a feature with very limited real world use. — Lundin, Nov 13 '15 at 07:12
@Lundin, *"you should avoid recursion in general, because it is a feature with very limited real world use"* --> very limited real world use? Maybe specifically for C programming for embedded systems it might have very limited real world use (I have no idea, as I don't have experience with that...). But in programming in general, recursion is actually tremendously useful and important building block! — Bruno Reis, Nov 13 '15 at 07:22
@BrunoReis It is not. Emphasis: _real world_, outside sheltered academic nonsense made up by mathematicians and computer scientist who have zero knowledge of how source code actually translates to machine code. On any system, recursion is slow, _very_ memory inefficient, _very_ dangerous and unreadable. The _only_ real-world use for recursion is a couple of searching and sorting algorithms. It is also a convenient way to cause stack overflow on purpose, when stress-testing a system. Every other use of recursion is poor programming practice. — Lundin, Nov 13 '15 at 07:35
@Lundin: you might need to research on modern programming languages, then. If you restrict the "real world" to C programming, then you are correct -- recursion like will always cause stack overflow and be a pain. If you widen your view of the "real world" a little bit and consider more modern programming languages, you will notice that many compilers are quite smart about optimizing tail recursions and completely avoiding stack overflow -- by the way, the compiled code, after optimization, would be just like a code with a "while" loop, or a bunch of "go to" statements. — Bruno Reis, Nov 13 '15 at 21:12
@Ludin: now, let me give you "real world" examples, instead of just "theory" (that you might not trust). Would you accept that "JavaScript" is a "real world" programming language, widely used all around (if you don't, then I suggest you take a look at statistics on GitHub and on StackOverflow; if you still don't, I give up)? Then you would love to know that ES6 (the new major version) supports tail call natively! Also, one very "standard" ES6 -> ES5 compiler also optimizes tail calls away! Ex: https://github.com/babel/babel/issues/256 . — Bruno Reis, Nov 13 '15 at 21:18
@Lundin: Need more "evidence"? Take a look at Scala's collection source code! You'll see plenty of recursion. Think Scala is "just academic research", used for very slow and theoretical stuff? Well, take a look at Apache Spark then: one of the top platforms for solving "real world" Big Data problems, all coded in Scala, using a ton of recursions. — Bruno Reis, Nov 13 '15 at 21:19
@Lundin: finally, to widen your view of the "real world" a bit more, I'd suggest you investigate a bit about "transpilers" -- when you "transform" source code in one form to another form, before finally compiling it. Pretty common practice nowadays, in tons of "non-academic" environments, that allows programmers to more easily express lots of algorithms, using nice abstractions such as recursions, that will be translated to more "low level" code (or, in your words, "real world code") without recursions and only then finally compiled to machine code. — Bruno Reis, Nov 13 '15 at 21:21
@Lundin: by the way, this is really not my area of expertise, but apparently even some C compilers will do optimization for recursive calls as well, since about 7 years ago (according to http://stackoverflow.com/a/34129). But then, each one will select which part of the world they want to call "the real world"... — Bruno Reis, Nov 13 '15 at 21:28
@BrunoReis This is tagged C, what's your problem? Dump a Javascript essay on someone who cares. If you want real world examples of why recursion in C is bad, [recursion killed and maimed multiple people](http://www.i-programmer.info/news/91-hardware/6995-toyota-code-could-be-lethal-.html). As for C compilers, they may or may not be able to do recursion unrolling, depending on how messed up it is. — Lundin, Nov 16 '15 at 07:18
@Lundin, my initial problem was specifically with your *very broad*, wrong assertion that I mentioned in my first comment: *"you should avoid recursion in general, because it is a feature with very limited real world use"*. As I mentioned multiple times, it definitely has a lot of very important real world use. If you restrict your assertion to your very specific and limited area of expertise, instead of a broad assertion about a real world that you don't seem to have experience with, I'm fine -- you wouldn't be spreading wrong information to other people. — Bruno Reis, Nov 16 '15 at 09:03

score 1 · Accepted Answer · answered Nov 13 '15 at 07:07

First function calls 1 as the argument and 1 is printed

then it enters the if statement

The count gets incremented

 fun(fun(fun(2)))

2 is printed and and enters if and

count is incremented to 3

fun(fun(fun(3))))

3 is printed.But this time it is doesn't enter the if instead 3 is returned

return(3)

and 3 is returned to the previous nested calls

 fun(fun(3))

this happens 4 times and hence the output

1233333

score 0 · Answer 2 · answered Nov 13 '15 at 04:04

0

fun(fun(fun(++count)));

Is basically equivalent to:

int tmp = fun(++count);
tmp = fun(tmp);
fun(tmp);

answered Nov 13 '15 at 04:04

Bobby Sacamano

540
4
15

score 0 · Answer 3 · answered Jul 28 '20 at 06:54

0

Firstly fun(1) will be called

Print 1

Fun(fun(fun++1)=fun(fun(fun(2)))

So,

fun(2) will be called

Print 2

Fun(fun(fun(3)))

Fun(3) called

Print 3

If confition false

Return 3, now

Fun(fun(3))

Again print 3

Return 3 then

Fun(3)

Print 3

Return 3

And recursion return back to the position of fun(2)

Fun(fun(fun(2))) will be fun(fun(3) //because 3 is returned

Fun(fun(3))

Print 3

Then return 3

Fun(3)

Print 3

And also return 3

So after all the things printed values will be 1 2 3 3 3 3 3

answered Jul 28 '20 at 06:54

Aditi Namdeo

1

2

Welcome to Stack Overflow. Could you please start off by taking the [tour], and then read the [formatting guide](https://stackoverflow.com/editing-help), then [edit] your answer so that the code is formatted into code blocks like those you can see in the question. – David Buck Jul 28 '20 at 07:34

score -1 · Answer 4 · answered Nov 13 '15 at 04:13

Calling a function like this is not really a recursion. You can say it nested function call. In your case, you are calling function fun() three times and passing the value returned by earlier call of function.

fun(fun(fun(++count)));

So, first fun() call will take a value ++count. Whereas the second fun() call will take the value returned by first call of function as parameter. Similarly, the third call will take a value returned by second call of fun() as parameter.

To understand things easily, you can consider following example

fun3(fun2(fun1(++count)));

In this example fun1() will take ++count as parameter. fun2() will take returned value by fun1() as parameter. Similarly, fun3() will take returned value by fun2() as parameter.

I hope this explains.

It is recursion in the sense that the calling function is the function that's being nested. — tangrs, Nov 13 '15 at 04:16

Recursion on Recursion in C

4 Answers4