CODEWITHSUNDEEP
crecursion
Ano Corff
Ano Corff

Reputation: 39

I am getting unexpected output

I assumed the output to be '0' for the following code but, I am getting the output as '3'.

#include<stdio.h>
int num_digit(int n);

int num_digit(int n)
{
    if (n == 0)
        return 0;
    else
        return 1 + num_digit(n/10);
}

int main() {
    int k  = num_digit(123);
    printf("%d\n",k);
    return 0;
}

Upvotes: 1

Views: 87

Answers (3)

Mayur
Mayur

Reputation: 2721

Recursion stack for your code is like below

1 + num_digit(123/10);
1 + num_digit(12/10);
1 + num_digit(1/10); //at this point your code will return 0 for num_digit(1/10)

and backtracking is like below

1+0=1
1+1=2
1+2=3

Hence the final answer is 3

Upvotes: 1

Subham Sarda
Subham Sarda

Reputation: 31

This is basic recursion. Just try to create a recursion tree for the program that you have written and you should be able to figure out why is the output that you see coming as 3.

You are expecting 0 as answer, only based on the last recursive call (terminating condition), but when a recursive call happens, there is a concept of activation records which are maintained in the form of Stack data structure.

The recursion tree will look something like what is shown in Recursion Tree for shared code

num_digits(123) = 1 + num_digits(12)
num_digits(12)  = 1 + num_digits(1)
num_digits(1)   = 1 + num_digits(0)
num_digits(0)   = 0

Using substitution:

num_digits(123) = 1 + (1 + (1 + (0)))

Please follow the parenthesis above clearly and you should be able to absolutely understand the output that you were getting out of the code that you wrote.

Upvotes: 2

Ano Corff
Ano Corff

Reputation: 39

The following link provides an excellent source for learning C Recursion and as @MFisherKDX pointed out help solve my confusion.

https://www.programiz.com/c-programming/c-recursion

After each time the recursion happens it returns a value. adding up all the values :

0+1 = 1
1+1 = 2
2+1 = 3

gives the answer as 3.

Upvotes: 2

Related Questions