What is recursion? And what are recursive algorithms.
I am taking a computer science class online and it is trying to explain recursion and recursive algorithms to me. I am really struggling to understand. I wrote an iterative factorial function:
local function factorial(num)
local finalAnswer = 1
if num > 1 then
for i = 1, num do
wait()
finalAnswer = finalAnswer * i
end
end
return finalAnswer
end
But now it wants me to write a recursive factorial function. I have no idea what that means and I would love it if someone could help me out. Here is the explanation that they gave for the recursive factorial function that I am supposed to write. Thanks!
0
1 answer
Recursion is mostly identified as a function calling itself. A lot of recusive functions haves a Base Case to get out of it or else it becomes an infinite loop. Recursion is essencially a different type of loop.
They work similarly to how you would traverse an array, but with enhanced capability. For example if you had a Model full of parts, you could loop through that like so:
for i,v in pairs(model:GetChildren()) do
print(i,v)
end
Now making it more complicated what if a child of that model had children of it's own? How do do you also get those?
That's where recursion can come in handy, here is an example:
function recurse(obj)
for i,v in pairs(obj:GetChildren()) do
print(i,v)
if #v:GetChildren() > 0 then
recurse(v)
end
end
end
for i,v in pairs(model:GetChildren()) do
print(i,v)
if #v:GetChildren() > 0 then
recurse(v)
end
end
Explaining how this works... The loop starts iterating through the model's children, and it will do so until it hits a child who has children of it's own. From there it will call the recurse() function and start iterating through the child's children. And the same process happens there. If one of the child's children has children it will call the function again, going another step deeper. This is just 1 example. (It does not require a Base Case since it's not really getting or setting anything, it's just looking at the contents).
Another example could be use to find and get a particular instance called "GetMe":
function recurse(obj)
for i,v in pairs(obj:GetChildren()) do
if v.Name == "GetMe" then
return v
end
if #v:GetChildren() > 0 then
return recurse(v)
end
end
return false
end
return recurse(model)
Let's say that the recurse() function has now been called 3 times, that means it is 3 layers deep in children of the Model. So how the return works is that the 3rd recurse() will return to the 2nd, and the 2nd will return to the first which would be the return recurse(model) statement.
For your factorial problem, you would use that principal:
function multiply(n)
if n >= 1 then
return n*multiply(n-1)
end
return 1
end
print(multiply(5))
-- Output
120
Basically each time it iterates through multiply(), it will take 1 off of n until you get to the base case which is just return 1, that's where it ends and start's is returns back the way it came. Return 1, return 2x1, return 3x2, return 4x6, return 5x24.
0
0
0
0