Small Basic - A First Look at Recursion

  • Article

A First Look at Recursion

First, take a look at these Goto resources:

Assuming you did, then you learned how to use the Goto keyword to repeat statements in a program.

Another way to get repetition is through recursion. After performing an action, a subroutine calls itself again, either directly or indirectly through another subroutine.

You’ll find a simple example in Listing 1...

 

Listing 1: Infinite recursion

1 ' Recursion1.sb

2 ' Demonstrates infinite recursion

3

4 SayHello()

5

6 Sub SayHello

7   TextWindow.WriteLine("Hello!")

8   SayHello()

9 EndSub

The program starts by calling the SayHello() subroutine (Line 4). The subroutine displays the string "Hello! " (Line 7) and then calls itself (Line 8). The second call starts the subroutine over, displays "Hello!" and then calls itself again. This third call displays "Hello! " and then calls itself again, and so on (the friendliest endless loop ever). A subroutine that calls itself, like SayHello() , is a recursive subroutine. The subroutine call at Line 8 is a recursive call.

But this subroutine has a serious problem; it never stops (actually, the program eventually crashes). For the recursion to be useful, you’ll need to limit the number of times you make the recursive call. So you’ll need to include a conditional check (like an If statement) in the subroutine, to decide each time whether it should make the recursive call again. As an example, write the recursive subroutine in Listing 2 to count from a number (which is held in a variable named counter) down to 0.

 

Listing 2: Counting down using a recursion

 1 ' CountDown.sb

 2 ' Counts down using recursion

 3

 4 counter = 5

 5 CountDown()

 6 TextWindow.WriteLine("")

 7

 8 Sub CountDown

 9   If ( counter >= 0 ) Then

10     TextWindow.Write( counter + " " )

11     counter = counter - 1

12     CountDown()

13   EndIf

14 EndSub

  

Output:

5 4 3 2 1 0

 

The main program starts by setting counter = 5 (Line 4) and then calls the CountDown() subroutine (Line 5). When the subroutine runs, it checks the value of the counter variable (Line 9). Since (5 ³ 0), your subroutine displays the number 5, followed by a space (Line 10), it decreases counter by 1 (Line 11), and calls itself again (Line 12). In the second call, because (4 ³ 0), the subroutine displays the number 4, decreases counter to 3, and calls itself again. This continues until the value of counter becomes zero. After it displays the number 0, the subroutine decreases counter by one (which makes counter = –1), then calls itself again. Since the If condition is false this time, your program doesn’t make any more recursive calls.

You could argue that this is a complicated way to write a program that counts from 5 down to 0, and that you could do this in a much simpler way. You’re right, but for some types of problems, recursion makes your program tasks simpler than you could possibly imagine!

The form of recursion used in the above example is a tail recursion because the recursive call is located at the very end of the subroutine. Small Basic also supports non tail-end recursion, where the  recursive call occurs somewhere in the middle of the recursive subroutine. We won’t discuss this type of recursion though (maybe later).

 

SELF-CHECK 

Write a program that asks your user her age. Then write a recursive subroutine that counts up from one to the user’s age.  

 

Leave a comment if you have any questions!

Learn more about Small Basic: https://blogs.msdn.com/b/smallbasic/

    

Small and Basically yours,

   - Ninja Ed & Majed Marji