Udostępnij za pośrednictwem

Small Basic - A First Look at Recursion

  • Artykuł

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

Comments

  • Anonymous
    April 30, 2015
    Hi, Ed, I'm working on a recursion program to generate a list of subsets from a whole set.  In particular, I'm looking to have it sorted in the Banker's Sequence as given in this paper:  applied-math.org/subset.pdf On page 6 of that paper is a chart, showing a two-dimensional array of binary values to indicate which elements are in the subset and which are not.  it's this table of 0's and 1's I'd like to generate.  I'm able to code a more general (unsorted) version of this, but I'm not able to recreate the Banker's Sequence using recursive code.  Further in that paper is a sample in C code, but the subroutines carry arguments, which is not available in Small Basic. Can you suggest how to code the Banker's Sequence using recursion in Small Basic? Thanks in advance!

  • Anonymous
    May 03, 2015
    Mark, fantastic question. I'm not sure. Can you ask in the Small Basic forum? social.msdn.microsoft.com/.../home That also helps because one person starts to answer the question some and gives us more ideas to improve the answer. Thanks!

  • Anonymous
    January 31, 2016
    Computers Today (part 1 of 6) blogs.msdn.com/.../computers-today.aspx ..... CS SPOTLIGHT: Girls in computer programming... why it matters!!! blogs.msdn.com/.../cs-spotlight-girls-in-computer-programming-why-it-matters.aspx ... Computational Thinking - Videos & Papers by Jeannette Wing blogs.msdn.com/.../computational-thinking-videos-amp-papers-by-jeannette-wing.aspx

  • Anonymous
    November 29, 2016
    Aw, this was an incredibly nice post. Taking the time and actual effort to create a really good article… but what can I say… I put things off a whole lot and never seem to get nearly anything done.

    • Anonymous
      January 06, 2017
      Thanks, Holly Health!