Recursion
Code and descriptions are mainly adapted from [Data Structures and Algorithms in Python].
Recursion makes one or more calls to itself during execution, or by which a data structure relies upon smaller instances of the very same type of structure in its representation.
Examples
Factorial function
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
Repetition is provided by the repeated recursive invocation of the function.
English Ruler (Fractal)
Fractal is a shape that has a self-recursive structure at various levels of magnification.
Due to the symmetry, an interval with a central tick length is composed of:
- An interval with a central tick length
- A single tick of length
- An interval with a central tick length
[Data Structures and Algorithms in Python], p154, Figure 4.3
# this reminds me of depth-first tree traverse
def draw_line(tick_length, tick_label=''):
line = '-' * tick_length
if tick_label:
line += ' ' + tick_label
print(line)
def draw_interval(center_length):
if center_length > 0:
draw_interval(center_length - 1)
draw_line(center_length)
draw_interval(center_length - 1)
def darw_ruler(num_inches, major_length):
draw_line(major_length, '0')
for j in range(1, 1 + num_inches):
draw_interval(major_length - 1)
draw_line(major_length, str(j))
time complexity: For , a call to draw_interval(c)
results in precisely lines of output.
Binary Search
The following is code2flow
:
binary_search:
nop;
binary_search(data, target, low, high);
if(low>high) {
False;
return;
}
else{
mid=(low+high)//2;
if(target==data[mid]) {
True;
return;
}
else if(target<data[mid]) {
//recursion
binary_search(data, target, low, mid-1);
loop binary_search;
}
else{
//recursion
binary_search(data, target, mid+1, high);
loop binary_search;}
}
The Python code is:
def binary_search(data, target, low, high):
if low > high:
return False:
else:
mid = (low+high) // 2
if target == data[mid]:
return True:
elif target < data[mid]:
return binary_search(data, target, low, mid -1)
else:
return binary_search(data, target, mid + 1, high)
Time complexity: for a sorted sequence with n
elements.
File Systems
The code for code2flow
:
recursion:
//recursion call
nop
**DiskUsage**(path);
//immediate disk space of current entry
total=size(path);
if(path represents a directory?){
while(has child entry in directory path?){
total+=**DiskUsage**(child);
loop recursion;
}
}
Return total;
return;
The file system's tree structure is:
The actual execution order is:
As can be seen, it is depth first
. The Python code is:
import os
def disk_usage(path):
total = os.path.getsize(path)
if os.path.isdir(path):
for file_name in os.listdir(path):
child_path = os.path.join(path, file_name)
total += disk_usage(child_path)
print('{0:<7}'.format(total), path)
return total
Recursion Run Amok
Element uniqueness problem using for
:
def unique1(S):
for j in range(len(S)):
for k in range(j+1, len(S)):
if S[j] == S[k]:
return False
return True
def unique2(S):
temp = sorted(S)
for j in range(len(S)):
if S[j] == S[j+1]:
return False
return True
A while
version of Fibonacci
is:
def fibonacci():
a = 0
b = 1
while True:
# report value, a, during this pass
yield a
future = a + b
a = b
b = future
The recursion is defined as
for n>1.
A bad recursion
version of Fibonacci
is:
def bad-fibonacci(n):
if n<=1:
return n
else:
return bad_finonacci(n-2) + bad_fibonacci(n-1)
Let denote the number of calls performed in the execution of bad_fibonacci(n)
, then
The reason why it's so inefficient is because of the way the Fibonacci number, , depends on the two previous values, and . But after computing , the call to compute requires its own recursive call to compute , as it does not have knowledge of the value of that was computed at the earlier level of recursion. That is duplicative work. Worse yet, both of those calls will need to (re)compute the value of , as will the computation of .
A better version in Python is:
def good_fibonacci(n):
if n <= 1:
return (n, 0)
else:
(a, b) = good_fibonacci(n - 1)
return (a + b, a)
It's good to visualize it in http://www.pythontutor.com/visualize.html#mode=edit