SET$-252$ C Programming #$2$

Homework $12$ Recursion $$ Part $1$

Reading$($s$)$: As needed.

Recursive: a procedure that calls itself.

Recursion: that act of a procedure calling itself.

Getting a procedure to call itself is easy. The tough part is getting it to stop.

Here is an example of a procedure that adds the whole numbers $1$ to $100.$

$($continued on the next page$)$

Step $1$

Type in the code in the above example and get it working. Be sure to follow all the coding standards $($e$.$g comment blocks$).$

Find out the maximum number of times a procedure can be called recursively on your machine. Put that number in comments somewhere. Tell me how much memory your computer has too because that can be limiting factor.

Write a procedure, AddNumbersInRange, that takes a starting value and a stop value as parameters. The procedure should recursively add all the numbers $($inclusive$)$ in the range.

Step $2$

Write a procedure that will recursively find the factorial of a number.

The factorial of a number is written as number followed by an exclamation point. For example, the factorial of $10$ is written as $10!.$ To find the factorial of a number, multiple the number by the factorial of the number minus one. So the factorial of $10$ is equal to $10*$ the factorial of $(101)$ which is $9$ factorial. The factorial of $9$ is equal to $9$ times the factorial of $8($which is $91).$ You do this until you get to the factorial of $1$ which is $1.$ F$($N$)=$ N $*$ F$($N$-1),$ where N $>1$ and F$(1)=1.$

For example: F$(10)$ is

$10!=10*9!$

$=10*9*8!$

$=10*9*8*7!$

$=10*9*8*7*6!$

$=10*9*8*7*6*5!$

$=10*9*8*7*6*5*4!$

$=10*9*8*7*6*5*4*3!$

$=10*9*8*7*6*5*4*3*2!$

$=10*9*8*7*6*5*4*3*2*1!$

$=10*9*8*7*6*5*4*3*2*1$

To do that with a For loop would be very easy:

intFactorial $=$ intNumber;

for$($ intIndex $=$ intNumber; intIndex $>1$; intIndex $-=1)$

$\{$

intFactorial $=$ intFactorial $*($ intIndex $1)$;

$\}$

Calculate the factorial for values $1-20$ and display the results. Display the results in two columns. Left column $110$ and the right column $1120.$

Find out number for which the largest factorial that can be computed with this method on your computer. Put that number in comments somewhere. BTW, it$$s definitely NOT the same number as in step #$1.$ The answer will surprise you $($or at least it should$).$

Please don$$t search the internet for the answers$/$code$.$ You can find it very quickly but that would defeat the point of the exercise.

$($continued on the next page$)$

Step $3$

Write a procedure that will recursively find the Fibonacci value of a number.

The Fibonacci of a number is equal to the Fibonacci value of the number minus one plus the Fibonacci value of the number minus two. This is usually written as:

F$($N$)=$ F$($N$-1)+$ F$($N$-2),$ where N $>1$ and F$(1)=1.$

The Fibonacci value of one and two is one.

For example: F$(5)$ is

F$(5)=$ F$(4)+$ F$(3)$

$=$ F$(3)+$ F$(2)+$ F$(2)+$ F$(1)$

$=$ F$(2)+$ F$(1)+1+1+1$

$=1+1+1+1+1$

Find out the number for which the largest Fibonacci value can be computed with this method on your computer. Put that number in comments somewhere.

MEGA EXTRA CREDIT

Find a magic square solution for a $6$x$6$ square using recursion. You can search the internet to find out what a magic square is but don$$t search for code examples. You don$$t get extra credit for copying and pasting. I$$ll know just by asking you a few questions whether or not you did the work.