Saturday 7 February 2015

Recursion(Recursion(Recursion(...)))

Recursion is a powerful property of many programming languages. Alex's SLOG called it "code-ception", which I thought was a catchy name and a spot on way to describe it. Just like a dream inside a dream inside a dream, a recursive function is a function that goes inside itself, and then goes inside itself, and so on (as many times as needed). The difference between Inception and Recursion is that in Inception you go, while in a dream, into dreams of different people, while in Recursion you go, while the code is being executed, into the same code. Hence, the title Recursion(Recursion(Recursion(...))).

Why is it useful?
Save space; save trees. Well, not physical trees (unless for some reason you want to print your code [but not print() your code]), but memory space. The alternative is writing several functions with if statements that call each other when needed. A clear problem appears as you realize that you would have to write a lot of code if many steps are needed!

Tracing Back 
Trace back is a good exercise when wanting to understand what a piece of recursive code does. Let's try tracing back the following piece of code:

def looper(L): '''
 (list) -> int
 
 Awful docstring that explains nothing.
 '''

 return sum([looper(x) for x in L]) if isinstance(L, list) else 5

(Oh! BTW, that is a new trick I learned from the labs. You can make a return statement while implementing an if statement)

These are the examples that we will trace back:
looper([]) --> 0 #since L has no elements, recursion does not take place

looper([17]) --> sum([looper(x) for x in [17])
-- > sum([5])
--> 5

looper([1, 2, 3, 4, [5, 6]]) --> sum([looper(x) for x in [1, 2, 3, 4, [5, 6]])
--> sum([5, 5, 5, 5, 10]) #we do not solve when the function is executed inside
--> 30

looper(['some', 'here', 5, ['hello', 'there']]) --> sum([looper(x) for x in ['some', 'here', 5, ['hello', 'there']]])
--> sum([5, 5, 5, 10])
--> 25

2 comments:

  1. I'm assuming you've seen the movie, "Inception" (if not, it's a must see!!)
    Nice example of tracing a recursive function, as well as including the comments. Keep up the good slogging!

    ReplyDelete
  2. Really like your slogging style: description + pictures + some examples. Looks pleasing to the eye. Good job!

    ReplyDelete