The Elegant loop - Recursion
Aug 10, 2015
Factorial!
Recursion is a programming concept whereby a function invokes itself. Recursion is typically used to solve problems that are decomposable into subproblems that are just like the original problem, but a step closer to being solved.
def factorial_maker(num)
if num == 1
return num
end #base case
result = num * factorial_maker(num-1)
return result
end
Print Num to 0
def ntooh (num)
if num == 0
return num
end
p num
ntooh(num-1)
end
Add Number from 0 to Num
def plus(num)
if num == 0
return 0
end
result = num + plus(num-1)
return result
end
More advance recursion - Regular Sort
Regular short is to find the smallest number in the array and then push to the new array. This operation cost n2 time. Not the best and the fastest way of doing it but with power of recursion, the code is clean and readable.
def regular_sort(arr)
result = []
smallest = arr.first
if arr.length == 0
return result
end
for i in 1..arr.length-1
if smallest >= arr[i]
smallest = arr[i]
end
end
arr.delete_at(arr.rindex(smallest))
result.push(smallest)
result+=stack_sort(arr)
end
Stack and Queue Sort
The purpose of these exercise is to 1. understand the stack and queue in the database and make sort function with limited methods. The stack_sort is to use 'pop' and 'push' only and queue_sort is to use 'shift and unshift'.
#Stack_Sort
def stack_sort(arr)
sorted_arr = []
smallest = arr.pop
temp = [smallest]
if arr.length == 0
return sorted_arr
end
while arr.length > 0
if smallest >= arr.last
smallest = arr.last
end
temp.push(arr.pop)
end
sorted_arr.push(smallest)
temp.delete_at(temp.index(smallest))
sorted_arr+=stack_sort(temp)
end
# Queue_Sort
def queue_sort(arr)
biggest = arr.shift
temp = [biggest]
sorted_arr = []
rest = []
if arr.length == 0
return sorted_arr
end
while arr.length > 0
if arr.first > biggest
biggest = arr.first
end
temp.push(arr.shift)
end
while temp.length > 0
if temp.first == biggest
sorted_arr.push(temp.shift)
else
rest.push(temp.shift)
end
end
sorted_arr+=queue_sort(rest)
end
The key of recursion is the base case and the 'trust'. You must trust the fact that your recursion function will return exactly what you will ask for. Base case will stop the function once the condition was NOT meet. Therefore this is a 'breaker'. It is also important that the function must specify what this recursion will return.