How can I convert this iterative loop to a recursive one?

Question

At the moment, I'm working on a fractal renderer for stuff like the Mandelbrot set for my computer science coursework, and I want to use recursion instead of iteration on the function below since it will get me more marks.

The original iterative function is below. (I've removed some parts of the function which are for rendering other fractals, but I haven't included them otherwise this would be too long)

function fractal:compute(x,y)
    iteration = 1
    local zx = 0
    local zy = 0
    while iteration < self.maxIterations and zx^2 + zy^2 < 4 do
        temp = zx
        if self.current == "Mandelbrot" then
            zx, zy = Mandelbrot(zx,zy,x,y)
        end
        iteration = iteration + 1
    end
    return iteration
end

function Mandelbrot(zx, zy, x, y)
    return zx^2-zy^2+x, 2*zx*zy+y
end

I've tried to do this with a few methods, like using:

x^2 + y^2 > 4 or iteration == maxIterations

as the base case but for some reason it doesn't seem to work- such as this:

function fractal:compute_Recursively(x,y, cx, cy, count)
    if count >= fractal.maxIterations or x^2 + y^2 >= 4 then
        return count
    else return self.compute_Recursively(x^2-y^2+cx, 2*x*y + cy, cx, cy, count+1)
    end
end

function formulae.Mandelbrot_Recursive(x, y, cx, cy, i)
    if i >= fractal.maxIterations or x^2 + y^2 >= 4 then
        return i
    else return formulae.Mandelbrot_R(x^2-y^2+cx, 2*x*y + cy, cx, cy, i+1)
    end
end

Answer 1

In my humble opinion, this is not the case when recursion would be useful. Since you need to count the iterations, special measures, like additional parameters, need to be taken to store the current iteration count.

However, below is the code, where you can choose recursive or non-recursive variants of the function by commenting out one of them. To make it more beautiful and hopefully, to get more points, the code is made somewhat more generic. It relies on a small library for complex numbers. Tables with methods are not used.

-- get complex.lua from https://codereview.stackexchange.com/questions/252982/complex-number-class-in-lua.
local complex = require 'complex'

--[[
Get the iteration, at which the recursive function exceeds the limit. Not recursive.

    @param function func -- the recursive function to check,
    @param number limit -- limit to exceed,
    @param number max_iterations -- maximum number of iterations,
    @return number -- iteration at which the limit is exceeded, but not more than max_iterations.
--]]
local function iteration (func, limit, max_iterations)
    local z, iteration = complex (0), 0
    while iteration < max_iterations and z:abs () <= limit do
        z, iteration = func (z), iteration + 1
    end
    return iteration
end

--[[
Get the iteration, at which the recursive function exceeds the limit. Recursive.

    @param function func -- the recursive function to check,
    @param number limit -- limit to exceed,
    @param number max_iterations -- maximum number of iterations,
    @param complex z -- current value in the series; 0 by default,
    @param number iteration -- the current iteration; 0 by default.
    @return number -- iteration at which the limit is exceeded, but not more than max_iterations.
--]]
local function iterationRecursive (func, limit, max_iterations, z, iteration)
    local z, iteration = z or complex (0), iteration or 0
    if iteration >= max_iterations or z:abs() > limit then
        return iteration
    end
    z, iteration = func (z), iteration + 1
    return iterationRecursive (func, limit, max_iterations, z, iteration)
end

--[[
    Generate f_c (z) = z^2 + c function for the given c.
    
    @param complex c
    @return function
--]]
local function makeMandelbrot (c)
    return function (z)
        return z ^ 2 + c
    end
end

local limit, max_iterations = 2, 100
local range = {-1, -0.5, 0, 0.5, 1}
for _, re in ipairs (range) do
    for __, im in ipairs (range) do
        local c = complex (re, im)
        local mandelbrot = makeMandelbrot (c)
        --local iter = iteration (mandelbrot, limit, max_iterations)
        local iter = iterationRecursive (mandelbrot, limit, max_iterations)
        print ('c = ' .. tostring (c) .. ':\t' .. tostring (iter) .. '  iterations')
    end
end