How would I go about making a recursive function?

I swear I thought I knew how recursion worked but then my friend asked me how to code subtractive division (how you were taught how to divide in second grade) and I tried and tried and I just couldnt figure out. Every idea I had ended up just being a chain of if else statements which definitly wasnt recursive. Now I am not asking how to make what I describe but rather asking for a “framework” in a sense on how to make recursive functions.

2 Likes

Recursive algorithms are good for working with problems that can be understood recursively. If you can divide a problem up into smaller parts that are either

a) trivial to solve separately, or
b) solved in the same way as the whole problem

then you can use Divide and Conquer the problem. Hope this helps.

Do you want hints for how to divide the problem up?

Recursive functions are essentially just functions that call themselves until they return the base condition. For example, here’s the recursive function that you were trying to make, it uses subtractive division until finding the input number divided by 5:

local function subDiv(x)
    if x == 5 then --This is the base condition and what we're solving for.
        print('Completed solving for '..x)
        return x
    else
        print('Recursing...')
        return subDiv(x-5) --This is how functions are usually called recursively-- through returns.
    end
end

subDiv(25)
1 Like

Maybe using this function:

function gcd(num1, num2)
	local divisors1 = {}
	local divisors2 = {}
	local common_divisors = {}
	for x = 1, num1, 1 do
		if num1 % x == 0 then
			table.insert(divisors1, 1, x)
		end
	end


	for x = 1, num2, 1 do
		if num2 % x == 0 then
			table.insert(divisors2, 1, x)
		end
	end

	for _, v in pairs(divisors1) do
		for _, v2 in pairs(divisors2) do
			if v == v2 then
				table.insert(common_divisors, 1, v)
			end
		end
	end	

	table.sort(common_divisors, function(a, b)
		return a > b
	end)
	return common_divisors[1]
end

Is not the best as you can compact it more but it works.

Edit: Here is a more compact version

local function gcd(a,b)
  if typeof(a) == "number" and typeof(b) == "number" and 
        a == math.floor(a) and b == math.floor(b) then
    if b == 0 then
      return a
    else
      return gcd(b, a % b) -- recursion
    end
  else
    error("Invalid argument to gcd (" .. tostring(a) .. "," .. 
          tostring(b) .. ")", 2)
  end
end

1 Like