# Qbasicnews.com

Full Version: Recursion challenge
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3
Do what you want, graphics, math, annoying sounds.... but do it recursively! (Recursion is based on using a function that calls itself)

Code:
```declare sub factorial&(x&) print factorial&(10) end function factorial&(x&) if x& then factorial&(x&)=x&*factorial&(x&-1) else factorial&=1 end function```
A graphical example:

Code:
```'Hilbert curve DECLARE SUB Hilbert (r1%, r2%, level%) SCREEN 12 PSET (0, 0) clr% = 12 Hilbert 2, 0, 8 a\$ = INPUT\$(1) END SUB Hilbert (r1%, r2%, level%) SHARED clr% IF level% THEN   Hilbert r2%, r1%, level% - 1   LINE -STEP(r1%, r2%), clr%   Hilbert r1%, r2%, level% - 1   LINE -STEP(r2%, r1%), clr%   Hilbert r1%, r2%, level% - 1   LINE -STEP(-r1%, -r2%), clr%   Hilbert -r2%, -r1%, level% - 1 END IF END SUB```
Come on guys, let's see some of your examples using recursion. Some applications that use it are:
Quick Sort
Traversing trees or lists, which include:
* Displaying organization charts
* parts explosion for manufacturing
* CPM (Critical Path Method) for controlling projects

You can come up with some too. Maybe something simpler than my examples where you can post the code.
*****
Recursion in QB is horribly inefficient, especially for time-intensive operations, like quicksort.

http://forum.qbasicnews.com/viewtopic.php?t=2176
Quote:Recursion in QB is horribly inefficient, especially for time-intensive operations, like quicksort.

http://forum.qbasicnews.com/viewtopic.php?t=2176
We agree that recursion is inefficient, especially in QB.

Your QuickSort example is iterative, as you yourself said. Most implementations were originally done recursively, and some converted later to iterative precisely because of the inefficiency.

For the purpose of this challenge, maybe you could convert your example to recursive.
*****
Just pointing that out, I'm far too busy with other..things
With recursion you can draw a tree
Code:
```DECLARE SUB tree (x%, y%, a!, l!, o%) CONST right = 3.1415926# / 2 CONST dec1 = .9, dec2 = .2, dec3 = .77 CONST inc1 = .2, inc2 = .3, inc3 = .98 RANDOMIZE TIMER SCREEN 12: WINDOW (240, 320)-(-239, -319) DO CLS tree (0), (-200), (0), 70, 10 t! = TIMER + 1: DO: LOOP UNTIL TIMER > t! LOOP UNTIL LEN(INKEY\$) SUB tree (x%, y%, a, l, o%) STATIC temp, temp1 IF o% THEN   PSET (x%, y%)   temp = (RND - .5) * dec3   temp1 = (RND - .5) * inc3   x% = x% + l * COS(a + temp1 + right) + temp   y% = y% + l * SIN(a + temp1 + right) + temp   LINE -(x%, y%)   tree (x%), (y%), (a + inc1), l * dec1, o% - 1   PSET (x%, y%)   tree (x%), (y%), (a - inc1), l * dec1, o% - 1 END IF END SUB```

..or create a maze.
I ran it. That's really neat, Antoni.
That's a good example of something that you would not attempt to do iteratively.
*****
Example of why recursion is a pain in Qbasic. This is a four-way recursive floodfill that causes QB to very quickly run out of stack space.
Code:
```declare sub fill(x, y, c) screen 7 '**** Something to fill **** circle (160, 100), 10, 15 fill 160, 100, 15 end sub fill(x, y, c)   '**** Base case ****     if point(x, y) = c then exit sub     pset(x, y), c   '**** Recurse ****   fill x - 1, y, c   fill x + 1, y, c   fill x, y - 1, c   fill x, y + 1, c end sub```

Quote:That's a good example of something that you would not attempt to do iteratively.

All algorithms that that can be implemented recursively can be implemented iteratively and vice-versa. The recursive algorithm for generating Gray code for example has a worst case ammortized time of O(n), but when re-implemented recursively, in addition to removing the overhead of the recursive calls the ammortized time can be reduced to O(1).

Not all algorithms improve in effeciency when re-implemented recursively though, the recursive Johnson-Trotter algorithm requires three arrays of size n, the iterative implementation requires five arrays and twice as much indexing. Most algorithms have trade-offs for being implemented either recursively or iterativley.
I had almost forgot about Gray's Code. A pattern of bytes or words where each byte/word differs by only one bit from the preceding byte/word. An engineer once wanted to use Gray's Code to test a modem he designed, so he asked a buddy of mine and me to write the program to generate the code. We did it in assembler, all straight-line code, no if's (no branching), and of course no recursion. Too bad I can't remember how we did it.

Do you have the iterative version of the algorithm?
*****
Pages: 1 2 3