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