Reverse a Linked List - Recursive Solution

Function to reverse a linked list - recursive solution

void reverse(struct node *pred, struct node *curr)
{
  if(curr)
  {
    reverse(curr, curr -> link);
    curr -> link = pred;
  }
  else
    first = pred;
}

void main()
{
  reverse(NULL, first);
}

Written by Munia Balayil

Count the Number of Nodes in a Linked List - Recursive Solution

Function to count the number of nodes in a linked list - recursive solution

int count(struct node *p)
// p is a pointer to the first node of the list.
{
  if(p)
    return 1 + count(p->link);
  else
    return 0;
}

Written by Munia Balayil

Function to count the number of nodes in a linked list - iterative solution

int count(struct node *first)
// first is a pointer to the first node
{
  struct node *p = first;
  int count = 0;
  while(p)
  {
    ++count;
    p = p->link;
  }
  // Final value of count gives the number of nodes
  // in the linked list.
  return count;
}

Written by Munia Balayil

GATE 2010 C Programming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

What is the value printed by the following C program?

#include <stdio.h>

int f(int *a, int n)
{
  if(n <= 0) return 0;
  else if(*a % 2 == 0) return *a + f(a + 1, n - 1);
  else return *a - f(a + 1, n - 1);
}

int main()
{
  int a[] = {12, 7, 13, 4, 11, 6};
  printf("%d", f(a, 6));
  return 0;
}

(A) -9
(B) 5
(C) 15
(D) 19

Answer
------
(C) 15

Explanation
-----------
f(12,....6, 6) = 12 + f(7,....6, 5)
f(7,....6, 5) = 7 - f(13,....6, 4)
f(13,....6, 4) = 13 - f(4,....6, 3)
f(4,....6, 3) = 4 + f(11,....6, 2)
f(11,....6, 2) = 11 - f(6, 1)
f(6, 1) = 6 + f(NULL, 0)
f(NULL, 0) = 0

Hence, 12 + (7 - (13 - (4 + (11 - (6 + (0)))))) = 15
Written by Munia Balayil

GATE 2011 C Progamming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Consider the following recursive function that takes two arguments

unsigned int foo(unsigned int n, unsigned int r)  {
  if(n > 0) return ((n % r) + foo(n / r, r));
  else return 0;
}

What is the return value of the function "foo" when it is called as foo(345, 10)?

(A) 345
(B) 12
(C) 5
(D) 3

Answer: (B) 12

5 + 4 + 3 + 0 = 12

What is the return value of the function "foo" when it is called as foo(513, 2)?

(A) 9
(B) 8
(C) 5
(D) 2

Answer: (D) 2

1 + 1 = 2

Written by Munia Balayil

Quick Sort Using Recursion in C

"Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space." - Wikipedia

Written by Munia Balayil

Merge Sort Using Recursion in C

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

"Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945." - Wikipedia

Related articles

---

Quick Sort Using Recursion in C
Heapsort in C
Bubble Sort in C
Selection Sort in C
Binary Search in C
Basic Stack Operations in C

Written by Munia Balayil