Data Structure Questions and Answers on Sum of n Natural Numbers using Recursion for Freshers

1. Which of the following methods can be used to find the sum of first n natural numbers?

a) Iteration
b) Recursion
c) Binomial coefficient
d) All of the mentioned

Answer: d

Explanation: All of the above mentioned methods can be used to find the sum of first n natural numbers.

2. Which of the following gives the sum of the first n natural numbers?

a) nC2
b) (n-1)C2
c) (n+1)C2
d) none of the mentioned

Answer: c

Explanation: The sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)C2.

3. Consider the following iterative solution to find the sum of first n natural numbers:

#include
int get_sum(int n)
{
      int sm = 0, i;
      for(i = 1; i <= n; i++)
        ________;
      return sm;
}
int main()
{
    int n = 10;
    int ans = get_sum(n);
    printf("%d",ans);
    return 0;
}

Which of the following lines completes the above code?

a) sm = i
b) sm += i
c) i = sm
d) i += sm

Answer: b

Explanation: The line “sm += i” completes the above code.

4. What is the output of the following code?

#include
int get_sum(int n)
{
      int sm, i;
      for(i = 1; i <= n; i++)
        sm += i;
      return sm;
}
int main()
{
    int n = 10;
    int ans = get_sum(n);
    printf("%d",ans);
    return 0;
}

a) 55
b) 45
c) 35
d) none of the mentioned

Answer: d

Explanation: Since the variable “sm” is not initialized to 0, it will produce a garbage value.

5. What is the time complexity of the above iterative method used to find the sum of the first n natural numbers?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b

Explanation: The time complexity of the above iterative method used to find the sum of first n natural numbers is O(n).

6. Consider the following code:

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return ________;
}
int main()
{
    int n = 5;
    int ans = recursive_sum(n);
    printf("%d",ans);
    return 0;
}

Which of the following lines is the recurrence relation for the above code?

a) (n – 1) +recursive_sum(n)
b) n + recursive_sum(n)
c) n + recursive_sum(n – 1)
d) (n – 1) + recursive_sum(n – 1)

Answer: c

Explanation: The recurrence relation for the above code is: n + recursive_sum(n – 1).

7. Consider the following code:

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return n + recursive_sum(n - 1);
}
int main()
{
     int n = 5;
     int ans = recursive_sum(n);
     printf("%d",ans);
     return 0;
}

Which of the following is the base case for the above recursive code?

a) if(n == 0)
b) return 0
c) return n + recursive_sum(n – 1)
d) none of the mentioned

Answer: a

Explanation: “if(n == 0)” is the base case for the above recursive code.

8. What is the time complexity of the above recursive implementation used to find the sum of the first n natural numbers?

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b

Explanation: The time complexity of the above recursive implementation used to find the sum of first n natural numbers is O(n).

9. Which of the following methods used to find the sum of first n natural numbers has the least time complexity?

a) Recursion
b) Iteration
c) Binomial coefficient
d) All of the mentioned

Answer: c

Explanation: Recursion and iteration take O(n) time to find the sum of first n natural numbers while binomial coefficient takes O(1) time.

10. What is the output of the following code?

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return n + recursive_sum(n - 1);
}
int main()
{
      int n = 5;
      int ans = recursive_sum(n);
      printf("%d",ans);
      return 0;
}

a) 10
b) 15
c) 21
d) none of the mentioned

Answer: b

Explanation: The above code prints the sum of first 5 natural numbers, which is 15.

11. How many times is the function recursive_sum() called when the following code is executed?

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return n + recursive_sum(n - 1);
}
int main()
{
     int n = 5;
     int ans = recursive_sum(n);
     printf("%d",ans);
     return 0;
}

a) 4
b) 5
c) 6
d) 7

Answer: c

Explanation: The function recursive_sum is called 6 times when the following code is executed.

12. What is the output of the following code?

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return n + recursive_sum(n - 1);
}
int main()
{
     int n = 0;
     int ans = recursive_sum(n);
     printf("%d",ans);
     return 0;
}

a) -1
b) 0
c) 1
d) runtime error

Answer: b

Explanation: The program prints the sum of first 0 natural numbers, which is 0.

13. What is the output of the following code?

#include
int recursive_sum(int n)
{
      if(n == 0)
        return 0;
      return n + recursive_sum(n - 1);
}
int main()
{
     int n = -4;
     int ans = recursive_sum(n);
     printf("%d",ans);
     return 0;
}

a) 0
b) -10
c) 1
d) runtime error

Answer: d

Explanation: The above code doesn’t handle the case of negative numbers and so the function recursive_sum() will be called again and again till the stack overflows and the program produces a runtime error.