Start New Discussion within our Software Development Community

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.

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;
	};
    }
}