How does recursion work here?(Below Code)

Question

#include<stdio.h>
void func(int x)
{
   if (x==0)
      return;
   else
   {
      func(--x);   
      printf("%d\t",x);
   }
}
void main()
{
    int k=2;
    func(k);
}

Output: 0 1

Why isn't the output 0 1 2?

When the function is called for the first time, the value of x is equal to 2. Then it should also get printed at the end. I am confused with this code. Can someone help me out?

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: **[How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/)** — NathanOliver, Feb 16 '17 at 18:47
The line ` if(x==0) return;` could hardly be clearer. If `x` is `0` then don't do the rest of this function. — François Andrieux, Feb 16 '17 at 18:48
As the next exercise - swap the `printf` and `func` lines. Then go and read about *head recursion* versus *tail recursion*. — Eugene Sh., Feb 16 '17 at 18:52
@FrançoisAndrieux What I am asking is it should print 0 1 2 . I am emphasizing on 2 because it belongs to the last activation record and technically it should print 2 but it ain't doing so. — Satyendra Yadav, Feb 16 '17 at 18:54
@SatyendraYadav You are printing after you decrement `i`. Try `func(i - 1)` instead. — François Andrieux, Feb 16 '17 at 18:55

score 1 · Answer 1 · edited Feb 16 '17 at 19:01

1

--x decreases the value of x and you do that before printing; that's why the output is 0 1 and not 0 1 2.

edited Feb 16 '17 at 19:01

Jonathan Leffler

730,956
141
904
1,278

answered Feb 16 '17 at 18:54

Axel Mejia

11
2

score 1 · Accepted Answer · edited Feb 16 '17 at 19:27

For starters it would be more correctly to declare the parameter as having type unsigned int. Otherwise decreasing the parameter with a negative value can result in a very long output sequence.

In each recursive call of the function the parameter at first decreased and after decreasing it prints the output.

func(--x);   
     ^^^^
printf("%d\t",x);

So if the function initially was called with the argument equal to 2 then it outputs value 1 because the argument was decreased.

Thus

func( 2 ) --> outputs 1
func( 1 ) --> outputs 0
func( 0 ) --> outputs nothing

Only the innermost function call outputs its value firstly.

If you want that the output would look like

0 1 2

then the function should be defined as it is shown in this demonstrative program

#include <stdio.h>

void func( unsigned int x )
{
    if ( x ) func( x - 1 );   
    printf( "%u\t", x );
}

int main(void) 
{
    func( 2 );
    putchar( '\n' );
}

The function output is

0   1   2

The function differs from the original function is that the argument itself is not decreased in the function call. It keeps its value unchanged.

if ( x ) func( x - 1 );   
               ^^^^^^ the variable x itself is not changed

If the recursive call occurs at the beginning of a method, it is called a head recursion. The method saves the state before jumping into the next recursive call.

Thecave3 · Answer 3 · 2017-02-16T19:07:54.200

0

You just have to swap the recursive call after the printf.

#include<stdio.h>
void func(int x){
if(x==0){printf("%d\t",x);
return;}
else{
     func(--x);   
     printf("%d\t",x+1);
    }
  }
int main(){
    int k=2;
    func(k);
}

edited Feb 16 '17 at 19:07

answered Feb 16 '17 at 18:52

Thecave3

762
12
27

2

How is it answering the question? – Eugene Sh. Feb 16 '17 at 18:53
Please explain more. – Thecave3 Feb 16 '17 at 18:54
If you printf first and then call you'll have the correct output – Thecave3 Feb 16 '17 at 18:55
1

This also reverses the order of the output. – François Andrieux Feb 16 '17 at 18:57
Just noticed, my bad i'll fix this now – Thecave3 Feb 16 '17 at 19:01

msc · Answer 4 · 2017-02-16T19:15:10.127

0

Here, first value of x is decrease and pushed onto the stack each time until x== 0 and then, the final result is accumulated in the exact reverse order of the initial recursive function call.

edited Feb 16 '17 at 19:15

answered Feb 16 '17 at 19:02

msc

33,420
29
119
214

How does recursion work here?(Below Code)

4 Answers4