You could implement recursive algorithms in ways that avoid risking stack overflow, i.e. by manually implementing a stack of variables or a stack of states.

It is better to implement combinators that take pieces of recursive definitions and do this work for you. It is particularly easy to do in C#, with its anonymous delegates.

The program below shows how to implement higher order functions that flatten recursion into iterative code that doesn't eat up the stack. Its output would be

``````remove the 2's from 24 and you get 3
7! = 4030
Unmirrored: <<<0>1<2>>4<5<7>>>
Mirrored:   <<<7>5>4<<2>1<0>>>``````

The program below is written in C# 3.0.

40 Views
``````using System;
using System.Collections.Generic;

class Flattening {

// This Tree type will be used in the mirror example.

class Tree<T> {
public T Value { get; private set; }
public Tree<T> Left { get; private set; }
public Tree<T> Right { get; private set; }

public Tree(T value, Tree<T> left, Tree<T> right) {
Value = value;
Left = left;
Right = right;
}
}

static void Main(string[] args) {
var makeOdd = Tail((int x) => x / 2, x => x % 2 == 1);

var factorial = Linear(
(int n) => m => n * m,
n => n - 1,
n => n == 0,
zero => 1);

Console.WriteLine("remove the 2's from 24 and you get {0}",
makeOdd(24));
Console.WriteLine("7! = {0}", factorial(7));

// reverses a binary tree, maintaining structure
var mirror = Binary<Tree<int>, Tree<int>>(
t => {
var val = t.Value;
return (l, r) => new Tree<int>(val, r, l);
},
t => t.Left,
t => t.Right,
t => t == null,
nullT => null);

// Draws a binary tree.
var draw = Binary<Tree<int>, string>(
t => (l, r) => "<" + l + t.Value + r + ">",
t => t.Left,
t => t.Right,
t => t == null,
t => "");

Func<int, Tree<int>, Tree<int>, Tree<int>> mk
= (n, l, r) => new Tree<int>(n, l, r);

var tree = mk(4,
mk(1, mk(0, null, null),
mk(2, null, null)), mk(5, null, mk(7, null, null)));

Console.WriteLine("Unmirrored: {0}", draw(tree));
Console.WriteLine("Mirrored:   {0}", draw(mirror(tree)));
}

// For each of our combinators, we define the behavior of the
// function f (the returned function) in terms of the argument
// functions.

// Tail recursion:
// f(x) | bc(x)     = x
//      | otherwise = f(g(x))
static Func<T, T> Tail<T>(Func<T, T> g, Func<T, bool> bc) {
return (T x) => {
while (!bc(x)) {
x = g(x);
}
return x;
};
}

// For linear recursion, we could write g(x, f(h(x))) instead
// of g(x)(f(h(x))), but the latter form lets the value of x
// be garbage collected sooner. We could also write
// g(ha(x), f(hr(x))) to allow the garbage collection of x --
// which would make our mirror definition in Main nicer but
// some other code less nice.

// Linear recursion:
// f(x) | bc(x)     = b(x)
//      | otherwise = g(x)(f(h(x)))
static Func<TIn, TOut> Linear<TIn, TOut>(
Func<TIn, Func<TOut, TOut>> g, Func<TIn, TIn> h,
Func<TIn, bool> bc, Func<TIn, TOut> b) {

return (TIn x) => {
var stack = new Stack<Func<TOut, TOut>>();

while (!bc(x)) {
stack.Push(g(x));
x = h(x);
}
TOut y = b(x);
while (stack.Count != 0) {
y = stack.Pop()(y);
}
return y;
};
}

// Binary recursion is brutal. The function 'computer' makes an
// action that takes an x and places the return value f(x) into
// the variable y, without any net modification to the stack.

// Binary recursion:
// f(x) | bc(x)     = b(x)
//      | otherwise = g(x)(f(hl(x)),f(hr(x)))
static Func<TIn, TOut> Binary<TIn, TOut>(
Func<TIn, Func<TOut, TOut, TOut>> g, Func<TIn, TIn> hl,
Func<TIn, TIn> hr, Func<TIn, bool> bc, Func<TIn, TOut> b) {

return (TIn x) => {
TOut y = default(TOut);
var stack = new Stack<Action>();

Func<TIn, Action> computer = null;
computer = (TIn value) => () => {
if (bc(value)) {
y = b(value);
}
else {
var combiner = g(value);
var left = hl(value);
var right = hr(value);
stack.Push(() => {
var leftOutput = y;
stack.Push(() => { y = combiner(leftOutput, y); });
stack.Push(computer(right));
});
stack.Push(computer(left));
}
};

stack.Push(computer(x));

while (stack.Count != 0) {
stack.Pop()();
}
return y;
};
}
}``````