



Recursion - Fibonocci





	The mathematical definition of the nth fibonacci number is as follows:









	A direct translation into a recursive function yields the following:



										function Fib_1(N : in Positive) return Positive is

										begin

												if (N=1) or (N=2) then

													return 1;

												end if;



												return Fib_1(N-1) + Fib_1(N-2);

										end Fib_1;





Fibonocci, Cont.





	An array-based nonrecursive version is as follows:



										function Fib_2(N : in Natural) return Natural is

											type Fib_Array_Type is 							array (1..N) of Natural;

											Fibs : Fib_Array_Type;

										begin

												Fibs(1) := 1;

												Fibs(2) := 1;



												for I in 3..N loop

														Fibs(I) := Fibs(I-1) + Fibs(I-2);

												end loop;



												return Fibs(N);

										end Fib_2;





Fibonacci, Cont.





	A non-array-based and nonrecursive version is as follows:



										function Fib_3(N : in Natural) return Natural is

											A,B,C : Natural;

										begin

												if (N=1) or (N=2) then

													return 1;

												end if;



												A := 1;

												B := 1;

												for I in 3..N loop

													C := A + B;

													A := B;

													B := C;

												end loop;



												return B;

										end Fib_3;





Fibonacci, Cont.



	Question: What are the running times for Fib_1, Fib_2, and Fib_3?



	Fib_2	O(n)

	Fib_3	O(n)





	In the case of Fib_1, the analysis is a bit more involved.



	Define T(n) to be the total number of recursive calls made in a call to Fib_1(n).  If follows that:









	In other words, if n=1, then the total number of calls made to Fib_1(n) is simply 1, if n=2, then the total number 
of calls made to Fib_1(n) is simply 1, and otherwise, if n>2, then the total number of calls made to Fib_1(n) is 
equal to the total number of calls made as a result of the call to T(n-1) plus the total number of calls made as a 
result of the call to T(n-2), plus 1, which is the original call to Fib_1(n).





Comparison of Running Times





	In general, it can be shown that T(n) is O(2n).  Consequently, the running time of Fib_1(n) is O(2n).

	Note that n is an exponent in O(2n).



	logn (logarithmic)	n (linear)	n2 (quadratic)	2n (exponential)



	0	1	1	2

	1	2	4	4

	2	3	9	8

	2	4	16	16

	3	5	25	32

	3	6	36	64

	3	7	49	128

	3	8	64	256

	4	9	81	512

	4	10	100	1024

	4	11	121	2048

	4	12	144	4096

	4	13	169	8192

	4	14	196	16384



Towers of Hanoi



type Peg_Type is Character range `A'..'Z';



procedure hanoi (n : in Positive; From : in Peg_Type; To : in Peg_Type; Aux : in Peg_Type) is

begin

		if (n=1) then

			Text_IO.Put("Move Disk From Peg: ");

			Text_IO.Put(From);

			Text_IO.Put(" To Peg: ");

			Text_IO.Put(To);

			Text_IO.New_Line;

			return;

		end if;



		Hanoi(n-1,From,Aux,To);



		Text_IO.Put("Move Disk From Peg: ");

		Text_IO.Put(From);

		Text_IO.Put(" To Peg: ");

		Text_IO.Put(To);

		Text_IO.New_Line;



		Hanoi(n-1,Aux,To,From);

end hanoi;



Towers of Hanoi





Hanoi(1,'A','B','C')



Move Disk From Peg: A   To Peg: B







Hanoi(2,'A','B','C')



Move Disk From Peg: A   To Peg: C

Move Disk From Peg: A   To Peg: B

Move Disk From Peg: C   To Peg: B







Hanoi(3,'A','B','C')



Move Disk From Peg: A   To Peg: B

Move Disk From Peg: A   To Peg: C

Move Disk From Peg: B   To Peg: C

Move Disk From Peg: A   To Peg: B

Move Disk From Peg: C   To Peg: A

Move Disk From Peg: C   To Peg: B

Move Disk From Peg: A   To Peg: B





Towers of Hanoi



Hanoi(3,'A','B','C')



Move Disk From Peg: A   To Peg: C

Move Disk From Peg: A   To Peg: B

Move Disk From Peg: C   To Peg: B

Move Disk From Peg: A   To Peg: C

Move Disk From Peg: B   To Peg: A

Move Disk From Peg: B   To Peg: C

Move Disk From Peg: A   To Peg: C

Move Disk From Peg: A   To Peg: B

Move Disk From Peg: C   To Peg: B

Move Disk From Peg: C   To Peg: A

Move Disk From Peg: B   To Peg: A

Move Disk From Peg: C   To Peg: B

Move Disk From Peg: A   To Peg: C

Move Disk From Peg: A   To Peg: B

Move Disk From Peg: C   To Peg: B
