12.1.3 Recursion

• What is recursion in programming?

  Function calls itself
• The base case in recursion stops when n is 0, returning 1
• The recursive step in the factorial function calls itself with n-1.
• What is the purpose of the base case in recursion?

  Stop the recursion
• To calculate `factorial(3)` recursively, the first step is `factorial(3)` calls `factorial(2)`, breaking the problem into smaller subproblems
• Steps to calculate `factorial(3)` using recursion

  1️⃣ `factorial(3)` calls `factorial(2)`

  2️⃣ `factorial(2)` calls `factorial(1)`

  3️⃣ `factorial(1)` calls `factorial(0)`

  4️⃣ `factorial(0)` returns 1

  5️⃣ The results are propagated back up

  6️⃣ `3 * 2 * 1 * 1 = 6`
• In recursion, a problem is broken down into smaller, similar subproblems until a base case is reached.
• What is recursion in programming?

  Function calls itself
• Recursion breaks down a problem into smaller subproblems
• The base case in recursion stops the function when n = 0.
• What is the purpose of the base case in recursion?

  Stops the recursion
• In the factorial function, the recursive step is n * factorial(n - 1)
• The base case in recursion calls the function with a smaller input.

  False
• What is direct recursion?

  Function calls itself directly
• Match the type of recursion with its characteristic:

  Direct Recursion ↔️ Function calls itself directly

  Indirect Recursion ↔️ Multiple functions call each other
• The base case in recursion prevents infinite loops by ensuring the function eventually terminates.
• What is recursion in programming?

  Function calls itself
• Recursion is a programming technique where a function calls itself within its own definition
• The base case in recursion is necessary to prevent infinite loops.
• What happens if a recursive function does not have a base case?

  Stack overflow error
• In the factorial function, the base case is when $n$ equals 0
• What is the purpose of the recursive step in recursion?

  Reduces input size
• The base case terminates the recursion, while the recursive step continues it.
• What is direct recursion?

  Function calls itself
• Indirect recursion occurs when multiple functions call each other
• What is the first step in implementing a recursive algorithm?

  Define the base case
• Which method is used to analyze the time complexity of recursive algorithms by solving recurrence relations?

  Substitution Method
• For the factorial function, the time complexity is $O(n)$ using linear recursion
• Divide and conquer recursion has a time complexity of $O(n \log n)$.
• What is the key difference between recursion and iteration?

  Recursion calls itself
• The base case in recursion ensures the function does not call itself infinitely
• The recursive step in recursion moves the function closer to the base case.
• What is an example of direct recursion?

  Factorial function
• Indirect recursion involves multiple functions calling each other indirectly
• In direct recursion, a function calls itself within its own definition.
• Match the type of recursion with its example:

  Direct Recursion ↔️ Factorial

  Indirect Recursion ↔️ Mutually recursive functions
• Steps to implement a recursive algorithm in Python:

  1️⃣ Define the base case

  2️⃣ Create the recursive step
• The base case in recursion stops the recursion and returns a simple value.
• Iterative methods use loops, while recursive methods call themselves
• What does time complexity measure in recursive algorithms?

  Runtime with input size