12.1 Recursion basics
12.2 Simple math recursion
n
depends on the summation to n - 1
.
1
.
rec_fact()
uses a base case of n == 0
, which works because, just like 1!
, 0! = 1
. However, the base case of n == 0
returns n
, which at this stage is
0
, and therefore zeroes out the rest of the computation.
n == 1
is not used in the function. When n
is
0
, the overall multiplication becomes
0
. The recursion begins returning once the n < 0
base case is reached, initially returning -1
. But the previous recursive call would return
0
, thereby zeroing out all computations and leaving an overall result of
0
.
12.3 Recursion with strings and lists
"madam"
is a palindrome, so the function will recognize the word as a palindrome.
len(word) == 0
, which is resolved with the condition len(word) <= 1
.
strip()
function removes a given letter from the beginning and end of the string, including repeated letters. When strip('m')
is used with
"madamm"
, the resultant string is
"ada"
.
list_num
has an extra 15, and other_list
has an extra 22.
12.4 More math recursion
gcd(24, 30)
results in 30 - 24 = 6
, so the next call is gcd(24, 6)
. Thereafter, other calls are gcd(18, 6)
, gcd(12, 6)
, and gcd (6,6)
for a total of four recursive calls after the initial function call.
gcd(13, 23)
results in 23 - 13 = 10
, so the next call is gcd(13, 10)
. Thereafter, other calls are gcd(10, 3)
, gcd(7, 3)
, gcd (4,3)
, gcd(3,2)
, gcd(2,1)
, and gcd(1,1)
for a total of eight calls.
12.5 Using recursion to solve problems
mid
being
3
, next mid
becomes
5
, and finally, mid
becomes
4
. The element found at index 4 is equal to the key
16
.
mid
being (0 + 13) // 2 = 6
. The next call has mid (7 + 13) // 2 = 10
. The next call has mid (11 + 13) // 2 = 12
. At this point, 86 < 99
, so the final call is to mid 11
, after which there is nowhere else to go.