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