Recursion challenge

[Antoni Gual]

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

[Antoni Gual]

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

[Moneo]

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.
*****

[Agamemnus]

Recursion in QB is horribly inefficient, especially for time-intensive operations, like quicksort.

http://forum.qbasicnews.com/viewtopic.php?t=2176

[Moneo]

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.
*****

[Agamemnus]

Just pointing that out, I'm far too busy with other..things

[Antoni Gual]

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.

[Moneo]

I ran it. That's really neat, Antoni.
That's a good example of something that you would not attempt to do iteratively.
*****

[LooseCaboose]

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

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.

[Moneo]

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?
*****