Scribd
Upload
4 views2 pages

Recursion Concepts in Python Explained

Chapter 4 of the Goodrich Python Book covers recursion, including the factorial function, binary search, linear recursion, and binary recursion. It explains the recursive definition of factorial, the steps and time complexity of binary search, and provides examples of linear and binary recursion with their respective complexities. Key concepts include the base case for recursion and the differences between linear and binary recursive calls.

Uploaded by

vandanasinghnagar34
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Recursion Concepts in Python Explained

Chapter 4 of the Goodrich Python Book covers recursion, including the factorial function, binary search, linear recursion, and binary recursion. It explains the recursive definition of factorial, the steps and time complexity of binary search, and provides examples of linear and binary recursion with their respective complexities. Key concepts include the base case for recursion and the differences between linear and binary recursive calls.

Uploaded by

vandanasinghnagar34
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Short Notes: Chapter 4 (Recursion) - Goodrich Python Book

4.1.1 - The Factorial Function

- The factorial of n (n!) is defined as:

n! = n * (n-1) * ... * 1, with 0! = 1

- Recursive definition:

n! = n * (n-1)!, for n > 0

- Base case: 0! = 1

- Common example to illustrate recursion.

4.1.3 - Binary Search

- Binary Search is a divide-and-conquer algorithm used on sorted sequences.

- Steps:

- Compare middle element to target.

- If equal -> return index.

- If smaller -> search right half.

- If larger -> search left half.

- Time Complexity: O(log n)

4.4.1 - Linear Recursion

- A recursive call that makes at most one recursive call per activation.

- Reduces problem size linearly.

- Example: sum of list elements:

def linear_sum(S, n):

if n == 0:

return 0

else:
Short Notes: Chapter 4 (Recursion) - Goodrich Python Book

return linear_sum(S, n-1) + S[n-1]

- Space Complexity: O(n)

4.4.2 - Binary Recursion

- Each call makes two recursive calls.

- Example: Fibonacci numbers:

def fib(n):

if n <= 1:

return n

else:

return fib(n-1) + fib(n-2)

- Time Complexity: O(2^n)

- Used when problems divide into two subproblems.

You might also like