Why would I use recursive functions if I can use a for loop?
Recently I asked a question about recursive functions in relation to a problem I was trying to solve. My main question here is: I can do all that the function could do in a for loop so what is better about recursion? Here is the recursive factorial function:
local function factorial(num)
if num > 1 then
return num * factorial(num - 1)
else
return 1
end
end
Here it is with a for loop instead:
local function factorial(num)
local finalAnswer = 1
if num > 1 then
for i = 1, num do
finalAnswer = finalAnswer * i
end
end
return finalAnswer
end
Is there something better about going from the top down? I mean suppose I wanted the number where the factorial stops multiplying to be greater than 1. For the recursive function I would have to do: local function factorial(num, baseCase) on line 1 and return num * factorial(num - 1, baseCase) on line 5. But in the second example I could do: local function factorial(num, baseCase) on line 1 and for i = baseCase, num do on line 7. That seems like it takes less effort for the code to execute. I don't know. There might be something major I am missing. That is why I am asking this question. So my question is: What is better about recursive functions than other methods? I hope you guys can help. Thanks!
0
1 answer
Recursion tends to be more writable and readable than iteration
A factorial function isn't really complex enough for you to see the advantages of recursion, but something like quick sort will.
Quick sort
First let's review what quicksort does:
1) it chooses a random value from the table and makes this the partition
2) it separates the values into those smaller than the partition and those bigger than the partition
3) it sorts those sub tables
4) it combines the smaller table, the partition then the bigger table
Implementation
Some code that I write will just be a port of some Haskell code so it will not exactly be the most performant. The Haskell code will be shown on top.
Recursive implementation
--[[
Haskell Quicksort
quickSort :: (Ord a) => [a] -> [a] --takes a list of orderable elements and outputs a list of orderable elements
quickSort [] = [] --base case, an empty table is already sorted
quickSort (p : xs) = let smaller = quickSort $ filter (< p) xs --sort the smaller set
bigger = quickSort $ filter (>= p) xs --sort the bigger set
in smaller ++ [p] ++ bigger --combine them all together
]]
local function quickSort(t)
if #t == 0 then
return {}
end
local partition = table.remove(t)
local smaller = {}
local bigger = {}
for i = 1, #t do
local val = t[i]
table.insert(val < partition and smaller or bigger, val)
end
smaller = quickSort(smaller)
bigger = quickSort(bigger)
table.insert(smaller, partition)
for i = 1, #bigger do
table.insert(smaller, bigger[i]) --append all elements from bigger to smaller
end
return smaller --now sorted
end
This implementation can be explained in a few sentences.
Quicksort on an empty table will yield an empty table because an empty table is already sorted.
If the table is not empty then get a partition from the table and separate values into those smaller than the partition and those bigger than the partition. Sort those sub tables and combine them all together.
This implementation makes sense, it's intuitive and it is easy to reason about. Now let's look at an iterative implementation
Iterative
--[[
Code from Stack Overflow
https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
public static void iterativeQsort(int[] arr) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(0);
stack.push(arr.length);
while (!stack.isEmpty()) {
int end = stack.pop();
int start = stack.pop();
if (end - start < 2) continue;
int p = start + ((end-start)/2);
p = partition(arr,p,start,end);
stack.push(p+1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
private static int partition(int[] arr, int p, int start, int end) {
int l = start;
int h = end - 2;
int piv = arr[p];
swap(arr,p,end-1);
while (l < h) {
if (arr[l] < piv) {
l++;
} else if (arr[h] >= piv) {
h--;
} else {
swap(arr,l,h);
}
}
int idx = h;
if (arr[h] < piv) idx++;
swap(arr,end-1,idx);
return idx;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
]]
local function newStack()
return {
pop = table.remove,
push = table.insert
}
end
local function swap(t, i, j)
t[i], t[j] = t[j], t[i]
end
local function partition(arr, p, s, e)
local l = s
local h = e - 1
local pivot = arr[p]
swap(arr, p, e)
while l < h do
if arr[l] < pivot then
l = l + 1
elseif arr[h] >= pivot then
h = h - 1
else
swap(arr, l, h)
end
end
local idx = h
if arr[h] < pivot then
idx = idx + 1
end
swap(arr, e, idx)
return idx
end
local function quickSort(arr)
local stack = newStack()
stack:push(1)
stack:push(#arr)
while #stack > 0 do
local e, s = stack:pop(), stack:pop()
if not (e - s < 2) then
local p = math.floor(s + (e - s)/2)
p = partition(arr, p, s, e)
stack:push(p + 1)
stack:push(e)
stack:push(s)
stack:push(p)
end
end
end
It's a big mess, it doesn't make sense and its confusing. This is the explanation provided by Stack Overflow
1) Push the range (0...n) into the stack
2) Partition the given array with a pivot
3) Pop the top element.
4) Push the partitions (index range) onto a stack if the range has more than one element
5) Do the above 3 steps, till the stack is empty
Sure, if you look at the code long and hard enough maybe you'll see it looking like that procedure explain above, but it's definitely harder to understand than the recursion code.
0
0