High yield ●●●

🔁 Functions & Recursion

Why it matters: Recursive output and "how many calls" questions are standard, and parameter passing (by value only) is a favourite trap.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

Depth of linear recursion f(n−1)
n + 1 frames (including the base case)
Calls for f(n) = f(n−1) + f(n−2)
C(n) = C(n−1) + C(n−2) + 1, C(0) = C(1) = 1
Binary recursion halving n
calls = O(log n) with one branch, O(n) with two
Stack space of recursion
depth × size of one frame
Horner loop total = x·total + a[i]
evaluates the polynomial; with x = 2 and all a[i] = 1 gives 2^n − 1

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Output of a recursive function (print before/after the call)
Draw the call tree and keep the printing order for before-call and after-call statements.
★★★
Value returned by a recursive function on an array
foo(S+1, size−1) walks the array one element at a time; track what each call adds.
★★★
Pass by value vs pointer
Mark which variables are copies and which are written through an address.
★★★
Evaluation order of arguments
Follow the question's stated order (right to left) and print as each function runs.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

11 real questions from the official GATE CSE papers (2016 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

11 questions · 0 correct of 0 attempted · marks 0 / 16

Year:
GATE 2025 CS1 · Q34NAT1 mark
Consider the following C program.
#include <stdio.h>
void foo(int *p, int x){
  *p=x;
}
int main(){
  int *z;
  int a = 20, b = 25;
  z = &a;
  foo(z,b);
  printf("%d",a);
  return 0;
}
The output of the given C program is ______.
GATE 2025 CS1 · Q61NAT2 marks
Consider the following C program.
#include <stdio.h>
int foo(int S[],int size){
  if(size == 0) return 0;
  if(size == 1) return 1;
  if(S[0] != S[1]) return 1+foo(S+1,size-1);
  return foo(S+1,size-1);
}
int main(){
  int A[]={0,1,2,2,2,0,0,1,1};
  printf("%d",foo(A,9));
  return 0;
}
The value printed by the given C program is ______.
GATE 2025 CS2 · Q63NAT2 marks
Consider the following C program:
#include <stdio.h>
int g(int n) {
  return (n+10);
}
int f(int n) {
  return g(n*2);
}
int main() {
  int sum, n;
  sum=0;
  for (n=1; n<3; n++)
    sum += g(f(n));
  printf ("%d", sum);
  return 0;
}
The output of the given C program is ______.
GATE 2024 CS2 · Q13MCQ1 mark
Consider the following C program. Assume parameters to a function are evaluated from right to left.
#include <stdio.h>

int g(int p) { printf("%d", p); return p; }
int h(int q) { printf("%d", q); return q; }

void f(int x, int y) {
  g(x);
  h(y);
}

int main() {
  f(g(10),h(20));
}
Which one of the following options is the CORRECT output of the above C program?
GATE 2024 CS1 · Q19MCQ1 mark
Consider the following C program:
#include <stdio.h>
void fX();
int main(){
  fX();
  return 0;}

void fX(){
  char a;
  if((a=getchar()) != '\n')
    fX();
  if(a != '\n')
    putchar(a);}
Assume that the input to the program from the command line is 1234 followed by a newline character. Which one of the following statements is CORRECT?
GATE 2020 · Q48NAT2 marks
Consider the following C functions.
int tob(int b, int* arr) {
  int i;
  for(i=0; b>0; i++) {
    if(b%2) arr[i]=1;
    else arr[i]=0;
    b = b/2;
  }
  return(i);
}
int pp(int a,int b) {
  int arr[20];
  int i, tot = 1, ex, len;
  ex = a;
  len = tob(b,arr);
  for(i=0; i<len; i++) {
    if(arr[i]==1)
      tot = tot * ex;
    ex = ex * ex;
  }
  return(tot);
}
The value returned by pp(3,4) is ______.
GATE 2019 Set 2 · Q18NAT1 mark
Consider the following C program:
#include <stdio.h>
int jumble(int x, int y){
  x=2*x+y;
  return x;
}
int main(){
  int x=2, y=5;
  y=jumble(y,x);
  x=jumble(y,x);
  printf("%d \n", x);
  return 0;
}
The value printed by the program is ______.
GATE 2019 Set 2 · Q26MCQ2 marks
Consider the following C function.
void convert(int n){
  if(n<0)
    printf("%d",n);
  else {
    convert(n/2);
    printf("%d",n%2);
  }
}
Which one of the following will happen when the function convert is called with any positive integer n as argument?
GATE 2018 · Q21NAT1 mark
Consider the following C program:
#include <stdio.h>
int counter = 0;
int calc (int a, int b) {
  int c;
  counter++;
  if (b==3) return (a*a*a);
  else {
    c = calc(a, b/3);
    return (c*c*c);
  }
}
int main (){
  calc(4, 81);
  printf ("%d", counter);
}
The output of this program is ______.
GATE 2017 Set 1 · Q35MCQ2 marks
Consider the following two functions.
void fun1(int n) {          void fun2(int n) {
  if(n == 0) return;          if(n == 0) return;
  printf("%d", n);            printf("%d", n);
  fun2(n - 2);                fun1(++n);
  printf("%d", n);            printf("%d", n);
}                           }
The output printed when fun1(5) is called is
GATE 2016 Set 1 · Q12MCQ1 mark
Consider the following C program.
void f(int, short);
void main()
{
  int i = 100;
  short s = 12;
  short *p = &s;
  __________ ; // call to f()
}
Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Common traps

Arguments are copies; only *p = … changes the caller.
foo(val--) passes the old value, so the recursion never shrinks.
A function printing after the recursive call prints in reverse order.
The order of evaluation of arguments is unspecified unless the question says otherwise.