recursive

The recursive algorithm has three characteristics:

  • Solving problems of size N is transformed into one or more smaller problems of the same structure, and then the solutions of large problems can be constructed from these smaller problems
  • The number of recursive calls must be finite
  • Recursion must have an end condition to terminate the recursion
Def factorial(n): if n == 1 else: Return factorial(n - 1) print(factorial(3)) def power(x, n): if n == 0: return 1 else: Return x * power(x, n-1) power(3,2)Copy the code
Def search(sequence, number, lower, upper): if lower == upper: Assert number == sequence[upper] return upper else: middle = (lower + upper) // 2 if number > sequence[middle]: return search(sequence, number, middle + 1, upper) else: return search(sequence, number, lower, middle) def search_2(sequence, number, lower, upper): if lower == upper: Assert number == sequence[upper] return upper else: middle = (lower + upper) // 2 If number < sequence[middle]: return search(sequence, number, lower, middle-1) else: return search(sequence, number, middle+1, upper)Copy the code
Def hannoi(n, from_, buffer, to_): If n == 1, select * from A to C; Print (from_, "-->", to_) return print(from_, "-->", to_) return print(from_, "-->", to_) return Buffer) # Move the last remaining plates numbered N from rod A from A to C Hannoi (1, from_, buffer, from_, to_) # Move the last remaining plates from rod B from buffer B to C Hannoi (n-1, buffer, from_, to_) hannoi(3,"A", "B", "C") A --> C A --> B C --> B A --> C B --> A B --> C A --> CCopy the code
Def separator_elem(list_): if len(list_) == 1: return list_ mid = len(list_) // 2 left = separator_elem(list_[:mid]) right = separator_elem(list_[mid:]) return merge(left, right) def merge(x, y): l, r = 0, 0 tmp = [] while True: if l >= len(x): tmp += y[r:] break elif r >= len(y): tmp += x[l:] break elif x[l] < y[r]: tmp.append(x[l]) l += 1 else: Tmp.append (y[r]) r += 1 return TMP print(separator_elem([2, 4, 2, 5, 1, 9, 0, 45, 4, 5, 99,3, 2])) 4, 4, 5, 5, 9, 45, 99]Copy the code