Recursion problem

This is a discussion on Recursion problem within the C Programming forums, part of the General Programming Boards category; its difficult for me to understand argument exchange in the transfer function . a detail explanation will be really helpfull. ...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    73

    Recursion problem

    its difficult for me to understand argument exchange in the transfer function . a detail explanation will be really helpfull.

    Code:

    /* The TOWERS OF HANOI- solver using recursion*/



    Code:
    #include<stdio.h>
    
         void transfer (int n, char from, char to , char temp);
    
    	 void main()
    
    	 {
    	   int n;
    	   printf(" Welcome to the TOWERS OF HANOI\n\n");
    	   printf("How many disks?");
    	   scanf("%d", &n);
    	   printf("\n");
    	   transfer (n,'L','R','C');
    	 }
    
    	 void transfer ( int n, char from, char to, char temp)
    
     {
    	  if(n>0)
    
    	  {
    	   transfer(n-1,from,temp,to);
    	   printf("Move disk %d from %c to %c\n",n, from,to);
    	   transfer(n-1, temp,to,from);
    	  }
    	   
    	  return;
    	 
    	 }

    in the void transfer function , argument from ,to, temp receives - L,R, M respectively. then within the bracket -

    Code:

    Code:
    {
    	   transfer(n-1,from,temp,to);
    	   printf("Move disk %d from %c to %c\n",n, from,to);
    	   transfer(n-1, temp,to,from);
    	  }
    in the first transfer what will receive by from=
    temp=
    to=

    and they will pass to void transfer function as well ?

    And for 2nd transfer what will received by temp, to , from and what they will transfer to void transfer function as well ?

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Let's assume n is 9.

    1st run) transfer(9,'L','R','C')

    where from = 'L', to = 'C', temp = 'R'

    Inside the function n>0 so transfer is called with transfer(9-1, 'L','R','C')

    2nd run) now we have n = 8, from = 'L', to = 'R', temp = 'C'

    Inside the function n>0 so transfer is called with transfer(8-1, 'L','C','R')

    ....etc

    Just track the variable values.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    73
    claudiu @ thanks for ur answer.

    when n=1 it will enter in the function . then - inside the function

    transfer (0,'L','C','R')

    then it will again go to the void transfer(0, 'L','R','C) . however , will not enter again in the bracket, because n>0 not valid. then , how the printf happen ?

  4. #4
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    The printf happens in the original function call.

    So, let's recap:

    when n=1 the transfer function is called.

    Inside the transfer function n>0 so another call is made.

    Inside the second call n>0 is false so the second call returns control to the first. The first then does the printf and makes a third call (the one after the printf). Nothing happens in there since n=0. The third call returns control to the first. The first has nothing more to do so it returns control to main (or its calling function).
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  5. #5
    Registered User
    Join Date
    May 2010
    Posts
    73
    claudiu @ thanks for your answer. the program feels bit tricky..... assume that n=3,

    I understand that for how it will print that : move disk 1 from L to R
    what will happen after that ?

    The first has nothing more to do so it returns control to main (or its calling function).
    it will print : move disk 2 from L to C

    but how ? probably I'm not bothering you . an explanation will be helpful

  6. #6
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Let's ignore the arguments for now. I feel that you understand how they get switched around. What you seem to have trouble with is returning from the recursion and what gets printed when.
    The only argument we will take into account is n.

    if n = 3, call function transfer(3,....) FROM main. We will call this transfer-original to be able to distinguish it form subsequent calls.

    In transfer-original n=3 so n>0 so transfer(2....) is called. We will call this transfer-I.

    In transfer-I n=2 so n>0 so transfer(1...) is called. We will call this transfer-II.

    In transfer-II n =1 so n>0 so transfer(0...) is called. We will call this transfer-III.

    In transfer-III n=0 so nothing gets executed except for the return statement at the end (which by the way is useless, the function would exit at that point anyway).

    We are now back in transfer II. Remember, in transfer II n had the value 1. The control is now returned to transfer II at the printf statement. After the print transfer II calls another transfer-III, we will call this transfer-III' (prime) to distinguish it from the first.

    In transfer-III' n = 0 so nothing executes, the function just returns. Control is now returned to transfer-II at the end of the if, so IT returns as well.

    We are now in transfer-I where n=2, at the printf statement of transfer-I. something gets printed then another transfer-II is created we will call this transfer-II'(prime).

    Transfer-II' will go through the same process as transfer II. It will create a transfer-III which does nothing, then printf, then a transfer-III' which also does nothing.

    Then control is returned to transfer-I after the if. Transfer-I returns to transfer-original. Transfer-original creates a new transferI which creates a new transfer-II, which creates a new transferIII, prints, then creates a transferIII', then this new transfer II prints then a new transferII' gets created in transferI which itself calls a transferIII, prints and then creates a transferIII'.

    I have to admit, I myself am lost at this point lol, but I think you get the point.
    Last edited by claudiu; 05-28-2010 at 10:09 AM.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  7. #7
    Registered User
    Join Date
    May 2010
    Posts
    73
    Its quite complex for me as a beginner........ however, thank you very much for your support.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 17
    Last Post: 09-21-2009, 10:50 PM
  2. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  3. Recursion problem
    By trnd in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 03:06 PM
  4. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 04:52 PM
  5. recursion problem
    By dustinc in forum C++ Programming
    Replies: 1
    Last Post: 10-29-2001, 04:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21