My function:
int num(int x) { if(x>0) num(x-1); else return 0; printf("%d",x); } This function takes a input x and prints the numbers from 1 upto x.I can't seem to understand how this works, can someone please elaborate. Thanks in advance!
- I assume it wasn't you who wrote the function. If I call int x = num (10), there is undefined behaviour. The return type should be void, and it shouldn't return anything in the else part. Awful code.gnasher729– gnasher7292015-02-23 08:47:46 +00:00Commented Feb 23, 2015 at 8:47
- @gnasher729 I originally wrote this code(with some modification) to find the multiplication table of a number n. It worked fine for my purpose but I didn't know the code blows(since I'm in the early learning phase of recursion). Thanksuser2829775– user28297752015-02-23 14:10:58 +00:00Commented Feb 23, 2015 at 14:10
- Not related to the question, but recursion isn't the right tool for what you're using it for. A loop will handle an arbitrarily-large number without growing the stack on each iteration.Blrfl– Blrfl2015-02-23 14:18:01 +00:00Commented Feb 23, 2015 at 14:18
- Thanks,I know,I just wanted to flex my "recursion muscles"since I understand iteration properly.user2829775– user28297752015-02-23 14:27:42 +00:00Commented Feb 23, 2015 at 14:27
Add a comment |
2 Answers
To solve this type of thing, it's often best to take a pen and paper and "pretend to be the computer running the code".
So, if we have a call of num(4), it will lead to:
if (4 > 0) // Yupp, 4 > 0 num(3); // x - 1 = 3 if (3 > 0) // Yupp num(2) if (2 > 0) num(1) if (1 > 0) num(0) if (0 > 0) // Nope goto else-part: return 0; skip else-part print(1); skip else-part print(2); skip else-part print(3) skip else-part print(4) 
- @Malt It's confusing because of I place the print statement inside if statement inside braces just before the function call, my output is from x to 1. But when I place the print statement inside if statement inside braces just after the function call, my output is from 1 to x. Can you please elaborate the functioning? Thanks.user2829775– user28297752015-02-23 14:59:34 +00:00Commented Feb 23, 2015 at 14:59
- Follow the logic. If you put the print at the beginning of the function, the calls to
num(3),num(2)etc happens after printing, so obviously, values printed will be "high to low". If you place it after the call tonum- either in the if or at the end, it will print in "low to high" order.Mats Petersson– Mats Petersson2015-02-23 21:58:29 +00:00Commented Feb 23, 2015 at 21:58
in my opinion, the easiest way of wrapping your head around recursion is starting from the end.
In every recursive function, there's a stopping condition. In your case it's else return 0; so the method will return 0 if the argument is zero or lower. That's simple. Now let's go backwards.
We know that num(0) returns 0 without doing anything else. So now we can now figure out what num(1) is. num(1) will call num(0) (which will return 0 and do nothing else), and then print x which is 1. Now we can backtrack and look at num(2). num(2) will call num(1), which we already covered, and then prints 2, so we can look at num(3) etc.
So for every number x, num(x) will simply print all numbers from 1 to x.
