User:Cameron Chandoke/Recursion

Introduction

Demonstration of tail call and non-tail-call recursion in J. These are merely for comparative study, as tail calls are not optimized (i.e., unrolled into an iterative loop) in J.

Also a small collection of classic recursive examples.

"Tail call" refers to the final function call executed within a given expression (i.e., the function call at the top of the call stack).

To say that a given recursive function uses "tail-call recursion" means that in each recursive case, the recursive call is the final call executed in the expression.

For example, the following recursive verb, which calculates factorial (equivalent to the primitive verb !):

1:`{{y * $:<:y}}@.{{*y}} 7

is not tail-recursive because in the recursive subexpression {{y * $:<:y}}, the final verb call is the call to * .

By contrast, the following implementation of factorial is tail-recursive:

1 [`{{(x*y) $: <:y}}@.{{*y[x}} 7

because the verb that is executed last within the recursive subexpression {{(x*y) $: <:y}} is the recursive verb $: .

In the wider world of functional programming, the significance of tail-call recursion is that many languages turn a tail-recursive expression into a while-loop under the hood, so that the number of possible "recursive" calls will not be limited by the size of the call stack. (J is not among these languages.)

Collected examples

Recursion scoping adverb:

R=: {{ u{{u y}} : (u{{x u y}}) }}   
   ($:@<: [ echo)^:*R@>: 2
3
2
1
0

Concat -- foldr recursion:

   ({.,$:@}.)^:(0~:#) i.10                               
0 1 2 3 4 5 6 7 8 9

concat -- foldl recursion (dyadic call):

   '' (}.@]$:~{.@],[)`[@.(0=#@]) i.10   
9 8 7 6 5 4 3 2 1 0

concat -- foldl recursion (monadic call):

   ''&$: : (}.@]$:~{.@],[)`[@.(0=#@]) i.10          
9 8 7 6 5 4 3 2 1 0

Note how  seed&$: : tailRecDef  allows for elegantly passing the seed to tacit “go” function in acc-style recursion without requiring a named helper function.

foldr factorial:

   1:`(* $:@<:)@.*"0 i.7            
1 1 2 6 24 120 720

foldl factorial (dyadic call):

   1 [`(* $: <:@])@.(*@])"0 i.7                         
1 1 2 6 24 120 720

foldl factorial (monadic call):

   1&$: : ([`(* $: <:@])@.(*@]))"0 i.7                 
1 1 2 6 24 120 720

bi-partition quicksort:

   (((<:#[) ,&$: (>#[)) (?@#{]))^:(1<#@~.)  10?.50       
4 6 22 28 29 33 39 40 44 45

tri-partition quicksort:

   (($:@(<#[), (=#[), $:@(>#[)) (?@#{]))^:(1<#)  10?.50  
4 6 22 28 29 33 39 40 44 45

Ackermann function with anonymous recursion:

   c1 =: >:@]               
   c2 =: <:@[ $: 1:        
   c3 =: <:@[ $: ($: <:)  
   ack=: c1`(c2 f.)`(c3 f.)@.(,&* i. 0:)M.
   (i.4) ack"0] 3
4 5 9 61