Recursion problem

**chaklader** · 05-28-2010

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 ?

**claudiu** · 05-28-2010

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.

**chaklader** · 05-28-2010

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 ?

**claudiu** · 05-28-2010

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).

**chaklader** · 05-28-2010

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

**claudiu** · 05-28-2010

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.

**chaklader** · 05-28-2010

Its quite complex for me as a beginner........ however, thank you very much for your support.

Thread: Recursion problem

Thread Tools

Search Thread

Display

Recursion problem

Similar Threads

problem with printing elements of a array using recursion program

Template Recursion Pickle

Recursion problem

Problem of understanding recursion

recursion problem