program to print a linked list in reverse order

The need: 

     This program is a program to prints a linked list in reverse order without actually reversing it (For reversing a given linked list have a look on program78 of this blog). This program is written to show how recursion becomes more useful. First it asks user to enter numbers to be entered into linked list then creates a linked list, prints it in same as given and reversed order.

The code: 

---------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
typedef struct linked_list
{
    int item;
    struct linked_list *next;
}node;

node *create_list();
void print_list(node *);
void print_list_in_reverse(node *);

int main()
{
    node *head=NULL;
    printf("This program creates a linked list and then prints it first in given order and then in reverse\n");
    printf("create a list by entering elements press -999 to end\n");
    head=create_list();
    printf("\nThe list is\n");
    print_list(head);
    printf("\nThe list in reverse order is");
    print_list_in_reverse(head);
    printf("\n");
    return 0;
}

node *create_list()
{
    int x;
    node *temp=NULL;
    scanf("%d",&x);
    if(x!=-999)
    {
        temp=(node*)malloc(sizeof(node));
        temp->item=x;
        temp->next=NULL;
        temp->next=create_list();
    }
    return temp;
}
void print_list(node *p)
{
    if(p)
    {
        printf("%d ",p->item);
        print_list(p->next);
    }
    else
    printf("\n");
}

void print_list_in_reverse(node *p)
{
    if(p)
    {
        print_list_in_reverse(p->next);
        printf("%d ",p->item);
    }
    else
    printf("\n");
}

---------------------------------------------------------

The need:

   The approach is nothing but basics of recursion.
If we say the recursion in create_list function in normal English, we'll say "It will take a number form user if it is not -999, a new node is created, data is filled in it and address of this node is returned else NULL is returned." because temp is initialised to NULL each time in the starting of function.

If we say the recursion in print_list function in normal English, we'll say "It will print the data of a node and then go for doing the same to the next node after that if present".

If we say the recursion in print_list_in_reverse function in normal English, we'll say "It will print the data of a node when all the node after that are printed or if there is no node after that node".

 

Remarks:

1. We can print linked list as it is (in the given order) without using extra storage or extra thinking. We can just use loops but if we are asked to write a program to print the linked list without actually reversing it, we can not do it by just using loops. What we can do is next point.

2. For that we have to create a stack and push addresses of all the elements of linked list on it starting from head to end. Then pop addresses one by one and print the corresponding data. This requires extra storage and extra thinking.

3. So in this program recursion is the way to do the same without extra thinking and without explicitly using extra memory and functions.

4. I wrote explicitly with stress because recursion actually uses its own stack (System stack). Now I am not going into these details.

getting nth term of fibonacci series using recursion

The need: 

     This program is written just to give example of writing programs with recursion. This program finds nth term of a fibonacci series. Given that first term is 1, second term is also 1 and for rest terms T(n)=T(n-1) + T(n-2) holds true.

The code: 
---------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
int fibo(int x);

int main()
{
    int n,Tn;
    printf("Enter which term do you want?\n");
    scanf("%d",&n);
    if(n>0)
    Tn=fibo(n);
    else
    exit(printf("term index entered should be natural number\n"));
    printf("T(%d) of fibonacci series = %d\n",n,Tn);
    return 0;
}

int fibo(int x)
{
    int term;
    if(x==1)
      term=1;
    else if(x==2)
      term=1;
    else
      term= fibo(x-1) + fibo(x-2);
    return term;
}

---------------------------------------------------------

Remarks:

1. This program may not give correct output if the desired term is after 40th term. This is because the later terms can not fit into int data-type of C and data overflows.
2. This type of recursion when one function calls 2 instances of itself, is called binary recursion.
3. This program was written just to show use of binary recursion. Personally I would suggest not to use a recursion which calls 2 or more instances because not only it uses more system resources but also slows down the program execution drastically. For fibonacci series without recursion see program38 of this blog.

programs to find sum of first n natural numbers with recursion

The need: 

     This is a simple programs to find sum of first n natural numbers with recursion explaining the example2 of previous to previous post. We know that natural numbers form a series whose first term is 1 and T(n)=n and this is obvious that sum upto n term = sum upto n-1 terms + nth term.

The code: 
---------------------------------------------------------

#include<stdio.h>
int get_sum(int x);

int main()
{
    int n,Sn;
    printf("Enter upto which number do you want sum?\n");
    scanf("%d",&n);
    Sn=get_sum(n);
    printf("S(%d) = %d\n",n,Sn);
    return 0;
}

int get_sum(int x)
{
    int SUM;
    if(x==1)
      SUM=1;
    else
      SUM= get_sum(x-1) + x;
    return SUM;
}

---------------------------------------------------------

finding nth term of the series using recursion

The need: 

     This is a simple program just to get start with recursion explaining the example1 of previous post. This is very specific purpose program. This program finds nth term of a series whose first term is 2 and T(n)=T(n-1) + 1; is given.

The code: 
---------------------------------------------------------

#include<stdio.h>
int get_term(int x);

int main()
{
    int n,Tn;
    printf("Enter which term do you want?\n");
    scanf("%d",&n);
    Tn=get_term(n);
    printf("T(%d) = %d\n",n,Tn);
    return 0;
}

int get_term(int x)
{
    int term;
    if(x==1)
      term=2;
    else
      term= get_term(x-1) + 1;
    return term;
}

---------------------------------------------------------

Recursion in C programming langauge

what is recursion?
  The word recursion bears meaning similar to self-repeating. In programming it can be useful for programmers. Recursion is mostly used when we work with series and linked lists. In mathematics you people may have seen recursion while working with series. There you might have encountered a problem in which n'th term of a series was given as a function of some previous term/terms and value of first term would be given. Let me remind you with examples. This is highly recommended that for you to go through the examples below and then proceed.

Example1:   A n'th term of a series is 1 more than the (n-1)th term. Find the 4th term of the series given that first term is 2.
   Solution: Given that. T(1)=2
      and T(n)=T(n-1) + 1;    ------>    Eq.-1   (n'th term as function of (n-1)th term)

      so T(4)=T(3) + 1;                       we'll write T(3) in terms of t(2)

           T(4)=T(2) + 1 + 1;               we'll write T(2) in terms of t(1)

           T(4)=T(1) + 1 + 1 + 1;         we'll write value of T(1)

           T(4)=2 + 1 + 1 + 1;

           T(4)=5     Ans.

In this way you could find any term of the series.

Example2: Find the sum of first 5 natural numbers.
   Solution: If you know what natural numbers are, you'll know that
     It is given that nth term is n.
      S(1)=1      (Sum upto/of first term)
      and S(n)=S(n-1) + n;    (We got S(n) as a function of S(n-1))
             because this is obvious that
             sum up to n terms =  sum up to (n-1) terms + nth term.

      we have to find out

      so S(5)=S(4) + 5;                       we'll write S(4) in terms of S(3)

           S(5)=S(3) + 4 + 5;               we'll write S(3) in terms of S(2)

           S(5)=S(2) + 3 + 4 + 5;         we'll write S(2) in terms of S(1)

           S(5)=S(1) + 2 + 3 + 4 + 5;  we'll write value of S(1)

           S(5)=1 + 2 + 3 + 4 + 5;

           S(5)=15     Ans.

In this way you could find sum up to any term in the series.

That was mathematical recursion. In this case mathematical function used to express nth entity in terms of (n-1)th entity is called recursion function or recursive function.

Recursion in programming is same as mathematical recursion with a little bit programming touch. You have seen that a function can call other function to achieve any particular task. In programming when a function calls itself, its called recursion in programming jargon. As you'll practice programs, you'll get to know more. Next 2 programs will be for solving the 2 examples given above.

  In further posts we'll see how recursion can be used with linked lists and trees.
wait for it :P.