Key Takeaway

ALWAYS follow the same rules for executing function calls when reading recursive code, as they are exactly the same for a recursive function.

Summary: Reading Recursive Code

Introduction to Recursion

• Recursive Definition:
  • A recursive function calls itself within its definition.
  • Example: The factorial function in mathematics is defined recursively.

Factorial Function Example

• Mathematical Definition:

  $$ n! = \begin{cases} 1 &\text{if } n = 0 \\ n*(n-1)! &\text{if } n > 0 \end{cases} $$

• C Code for Factorial:

  int factorial(int n) {
    if (n <= 0) {
      return 1;
    }
    return n * factorial(n-1);
  }
  

  • Line 1: Declares the function factorial that takes an int and returns an int.
  • Line 2: Checks if \( n \leq 0 \).
  • Line 3: If true, returns 1.
  • Line 5: Otherwise, returns \( n \times \text{factorial}(n-1) \).

Execution of Recursive Functions

• Following the Same Rules:
  • The rules for executing recursive function calls are the same as for non-recursive functions.
  • When encountering a function call, create a new stack frame, set the parameter values, and move the execution arrow to the start of the function.
• Step-by-Step Execution:
  • Line 5: Calls factorial(n-1).
  • New Stack Frame: Created for factorial(n-1).
  • Return: The result of factorial(n-1) is multiplied by n and returned.

Understanding Through Execution

• Visualize Execution:
  • Draw stack frames to track the recursive calls and their parameters.
  • Follow the execution arrow to understand the flow of the recursive calls.
• Next Steps:
  • Watch a step-by-step execution video to see how recursive code execution follows the familiar rules of calling and returning from functions.

Conclusion

ALWAYS remember that recursive functions follow the same execution rules as non-recursive functions. Understanding these rules helps in reading and tracing recursive code effectively.

Question 1

Which one of the following best describes recursion

1 point