FIT1008 Lecture Notes - Lecture 8: Arity, Decomposition
18 Jun 2018
School
Department
Course
Professor
Recursion
!"#$%&'"("%()*'"+)$,%'-",."#$%&/0*"#1,+)$,%'-#"$2"34'"#(-'"5/06"(#"34'"$)/*/0(%
7)$#8
9/-+%')"3$"#$%&'
:
;(<4"#1,+)$,%'-"/#"#$%&'6"=/34"34'"#(-'"(%*$>"103/%"34'."<(0",'"#$%&'6"=?$"
21)34')")'<1)#/$0#"@,(#'"<(#'A
:
B()*'"+)$,%'-"-1#3",'8
C'<$-+$#(,%'"/03$"#-(%%')"#1,+)$,%'-#
○
D3"#$-'"+$/03>"#1,+)$,%'-"-1#3",'"#$%&(,%'"=/34$13"21)34')"
6'<$-+$#/3/$0
○
E$-,/0'"34'#'"#$%13/$0#"3$"<$-+13'"#$%13/$0"3$"$)/*/0(%"+)$,%'-
○
:
def solve(problem):
if problem [is simple]:
[solve problem directly]
else:
[decompose into subproblems p1,2,…]
solve(p1)
solve(p2)
…
[combine solutions to solve problems]
Non+tail-recursive
F'*G"2(<3$)/(%>"0$0"3(/%H)'<1)#/&'I"HHHHHHJ"0"K"L@MA"!"L@0A
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
F'*G"N/,$0(<</>"0$0H3(/%")'<1)#/&'I"HHHHHHJ"L@O0A
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-2) + fib(n-1)
E$-+%'P/3.
D)/3.8
Q0()."!"("#/0*%'")'<1)#/&'"<(%%"@(%%"+)'&/$1#"<$6'A
:
R/0()."!"O")'<1)#/&'"<(%%#"@)'<1)#/&'"#$)3#>"%(3')A
:
0H0()."!"0")'<1)#/&'"<(%%#:
C/)'<3S
C/)'<3"!")'<1)#/&'"<(%%#"-(6'"3$"34'"#(-'"210<3/$0:
T06/)'<3?-131(%"!"3$"J!"O"-'34$6#"@'*G"-'34$6"+"<(%%#"-'34$6"U>"=4/<4"/0"
31)0"<(%%#"+"(*(/0A
:
Tail-recursion
!"34'")'#1%3"$2"34'")'<1)#/&'"<(%%"/#"34'")'#1%3"$2"34'"210<3/$0
V$34/0*"/#"6$0'"/0"34'"=(.H,(<5:
E%$#'#3"3$"/3')(3/$0"H<(0",'"3)(0#2$)-'6"=/34$13"W#3$)/0*W:
Q#'21%"2$)"<$-+/%')"$+3/-/#(3/$0:
7)$#8
;22/</'03:
E(0"'(#/%.",'"3)(0#2$)-'6"/03$"/3')(3/&'"&')#/$0:
E$0#8
V$3"<%'()"(3"2/)#3:
F'*G"2(<3$)/(%>"3(/%H)'<1)#/&'I
def factorial(n):
return factorial_aux(n, 1)
def factorial_aux(n, result):
if n == 0:
return result
else:
return factorial_aux(n-1, result*n)
F'*G"N/,$0(<</>"3(/%H)'<1)#/&'I"HHHHHHJ"L@!A
def fib(n):
return factorial_aux(n, 0, 1)
def fib_aux(n, before_last, last):
if n == 0:
return before_last
else:
return fib_aux(n-1, last, before_last + last)
Week$8:$recursion
N)/6(.>"MX"Y10'"OZM[
MM8\]
Document Summary
= solve a large problem by solving subproblems of the same kind as the original. Each subproblem is solved with the same algo, until they can be solved w/o further recursions (base case) At some point, subproblem must be solvable without further decomposition. Combine these solutions to compute solution to original problem def solve(problem): if problem [is simple]: [eg. factorial, non tail-recursive] ------> n * o(1) = o(n) def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) [eg. fibonacci, non-tail recursive] ------> o(2n) def fib(n): if n == 0 or n == 1: return n else: return fib(n-2) + fib(n-1) Unary = a single recursive call (all previous code) Binary = 2 recursive calls (recursive sorts, later) Binary = 2 recursive calls (recursive sorts, later) n-nary = n recursive calls. Direct = recursive calls made to the same function.
