Basic Programming 101: Session II

All About Looping

Writing a computer program that calculates Factorial and prints the result tells you almost everything you'll ever need to know about programming computers. Factorial requires an if statement (should I stop at 0! or keep going and calculate N*(N-1)!), it requires an input statement (Factorial of what number) and an output statement (print the result).

This example calculates Factorial two separate ways. It's the same calculation and produces the same result, although each method uses a different technique: (1) for loop and (2) recursion.

For Loop

In this first part, we use a "for loop", which iterates over the numbers from 1 to N, multiplying them all together to get the answer N! = N * (N-1) * ... * 3 * 2 * 1.

10 input "Give me a number? ",a

20 gosub 2000

30 print "Looping: ";str$(a);"! = ";f

50 end

2000 f = 1

2010 for i = 1 to a

2020 f = f*i

2030 next i

2040 return

Line 20 (gosub 2000), jumps to 2000, sets 'f' equal to 1, and then line 2010 runs through all the numbers from 1 to 'a', finding their product and storing the value in 'f'. Line 2040 returns from the subroutine (back to line 30). Notice line 30 prints the resulting product, which is stored in 'f'.

The for loop is located on lines 2010, 2020 and 2030. Those lines do all of the work to compute Factorial.

Recursion

The second method to compute Factorial uses recursion. In this case, we take advantage of the fact that N! = N * (N-1)!. Rather than loop explicitly, we create a subroutine (in this case a special kind of subroutine known as a function) which calculates Factorial using itself.

3000 sub factorial(n)

3010 if (n < 1) then

3020 factorial = 1

3030 else

3040 factorial = n*factorial(n-1)

3050 endif

3060 end sub

Line 3000 starts the function by naming it ("factorial") and telling the computer it takes one variable ('n'). Line 3010 is the "if statement", it makes sure the recursion doesn't go on forever. In this case, we stop if 'n' is ever less than 1. If 'n' is not less than 1, line 3040 tells the computer to calculate the factorial of 'n' by multiplying n and the result of factorial(n-1); just like the mathematical definition. Line 3060 ends the subroutine. The value to be returned is stored in a variable 'factorial', the same name as the function.

One last item, the subroutine needs to be called:

40 print "Recursion: ";str$(a);"! = ";factorial(a)

Run the program to get the following:

Give me a number? 6

Looping: 6! = 720

Recursion: 6! = 720

Same result, two different methods, one using a for-loop and the other using a subroutine and recursion.