Unit 4: Functions and recursion - Subjective Questions

A function call is an expression that instructs Python to execute a function. It consists of the function name followed by parentheses containing zero or more arguments.

General syntax:

function_name(argument1, argument2, ...)

Example:

result = max(12, 25)

Python evaluates this call as follows:

• It evaluates the arguments 12 and 25.
• It transfers control to the built-in max() function.
• The function compares the supplied values.
• It returns 25 to the calling statement.
• The returned value is assigned to result.

A function call may be used in an assignment, an expression, another function call, or as an independent statement. For example, print(abs(-8)) contains a nested call: abs(-8) is evaluated first, and its result is passed to print().

Python functions can be classified as follows:

• Built-in functions: These are directly available without importing a module. Examples include print(), len(), type(), abs(), and max().
• Module functions: These are defined inside modules and usually require the module to be imported. For example, after import math, the square-root function is called as math.sqrt(25).
• User-defined functions: These are created by the programmer using the def keyword.

Example of a user-defined function:

def square(number):
    return number * number

print(square(6))

The output is 36.

The main differences concern their origin and availability. Built-in functions are always available, module functions belong to imported libraries, and user-defined functions are written to solve application-specific problems.

Type conversion is the explicit conversion of a value from one data type to another by the programmer. Conversion functions such as int(), float(), str(), and bool() are used.

Example:

age_text = "20"
age = int(age_text)

Here, the string "20" is explicitly converted into the integer 20.

Type coercion is an automatic conversion performed by Python while evaluating a compatible expression. It commonly occurs among numeric types.

result = 5 + 2.5

Python converts the integer 5 to the floating-point value 5.0, producing 7.5.

Difference:

• Type conversion is requested explicitly by the programmer.
• Type coercion is performed implicitly by Python.
• Python does not coerce unrelated types in many cases. For example, "5" + 2 raises a TypeError; the programmer must write int("5") + 2.

Python provides several built-in conversion functions:

• int(value) converts a compatible value to an integer. For example, int("42") gives 42, while int(4.9) gives 4 by discarding the fractional part.
• float(value) converts a compatible value to a floating-point number. For example, float("3.5") gives 3.5.
• str(value) creates the string representation of a value. For example, str(25) gives "25".
• bool(value) converts a value to True or False. Values such as 0, 0.0, None, "", and empty collections are false; most other values are true.

Limitations and errors:

• int("4.5") raises a ValueError because the string is not an integer literal.
• float("hello") raises a ValueError.
• int(None) raises a TypeError.
• bool("False") is True because it is a non-empty string.

Therefore, input should be validated before conversion when invalid data is possible.

The math module provides mathematical functions and constants for real-number calculations. It can be imported using import math.

Important members include:

• math.sqrt(x): returns the square root of .
• math.ceil(x): returns the smallest integer greater than or equal to .
• math.floor(x): returns the largest integer less than or equal to .
• math.pow(x, y): calculates and returns a float.
• math.factorial(n): calculates for a non-negative integer.
• math.sin(x) and math.cos(x): calculate trigonometric values, where is in radians.
• math.pi: provides an approximation of .

Example:

import math

radius = 4
area = math.pi * math.pow(radius, 2)
root = math.sqrt(81)
print(area, root)

The area is calculated using , and root becomes 9.0. Module qualification such as math.sqrt() also makes the source of each function clear.

A new function is defined using the def keyword. The usual steps are:

1. Select a meaningful function name.
2. Specify parameters inside parentheses.
3. End the function header with a colon.
4. Write an indented function body.
5. Use return when the function must send a result to its caller.
6. Call the function with appropriate arguments.

Example:

def rectangle_area(length, width):
    area = length * width
    return area

result = rectangle_area(8, 5)
print(result)

Here:

• rectangle_area is the function name.
• length and width are parameters.
• 8 and 5 are arguments.
• The function calculates .
• The return statement sends 40 back to the caller.

Defining functions improves reuse, readability, testing, and maintenance by placing a task in one named block.

Parameters are names listed in a function definition. Arguments are the actual values supplied when the function is called.

def greet(name, message="Welcome"):
    return message + ", " + name

Here, name and message are parameters.

Types of arguments:

• Positional arguments: Matched according to position. greet("Asha", "Hello") assigns "Asha" to name and "Hello" to message.
• Keyword arguments: Matched using parameter names. greet(message="Good morning", name="Ravi") is valid even though the order is changed.
• Default arguments: A parameter uses its predefined value when the caller omits it. greet("Asha") uses "Welcome" as the message.

Required parameters must normally appear before parameters with default values in a function definition. Keyword arguments improve readability, while default arguments make parameters optional.

The scope of a variable is the region in which its name can be accessed.

• A local variable is created inside a function and can normally be accessed only inside that function.
• A global variable is defined outside all functions and can be read from functions.
• A local variable with the same name as a global variable hides the global name inside that function.

Example:

count = 10

def show():
    count = 5
    print(count)

show()
print(count)

The function prints 5, while the final statement prints 10. The two assignments refer to different variables.

To reassign a global variable inside a function, Python requires the global statement:

count = 10

def update():
    global count
    count = count + 1

Excessive modification of global variables should be avoided because it creates hidden dependencies. Parameters and return values usually provide clearer data flow.

A fruitful function calculates and returns a value that can be stored or used in another expression.

def cube(x):
    return x ** 3

answer = cube(4)

Here, cube(4) returns 64.

A non-fruitful function primarily performs an action, such as displaying output, and does not explicitly return a useful result.

def display_cube(x):
    print(x ** 3)

If a function reaches the end of its body without executing an explicit return, Python automatically returns None. A bare return also returns None.

The distinction is important because a printed value is not the same as a returned value. A returned result can be assigned, passed to another function, or included in an expression, whereas a value merely printed by the function cannot directly be reused.

Function composition means using the result of one function as the argument of another function. In a nested call, Python evaluates the innermost call first.

For the expression:

math.sqrt(abs(-49))

Python evaluates it in these steps:

1. The innermost call abs(-49) is evaluated.
2. abs() returns the absolute value, so the intermediate result is 49.
3. The expression becomes math.sqrt(49).
4. math.sqrt() returns 7.0.

Therefore, the final result is 7.0.

Another example is:

print(round(math.sqrt(20), 2))

Here, math.sqrt(20) is calculated first, round(..., 2) rounds the result to two decimal places, and print() displays it. Function composition makes complex operations concise, although intermediate variables may improve readability.

Recursion is a programming technique in which a function calls itself, directly or indirectly, to solve a smaller version of the same problem.

A correct recursive function normally contains:

• Base case: A condition that can be solved immediately without another recursive call. It stops the recursion.
• Recursive case: A step that reduces the original problem to a smaller problem and calls the same function again.
• Progress toward the base case: Each call must modify its input so that the base case will eventually be reached.

Example:

def countdown(n):
    if n <= 0:
        print("Stop")
    else:
        print(n)
        countdown(n - 1)

The condition n <= 0 is the base case. The call countdown(n - 1) is the recursive case. Since n decreases on every call, the computation eventually terminates. Without a reachable base case, recursion continues until Python raises a RecursionError.

For a non-negative integer , factorial is defined as:

The recursive definition is:

and, for ,

Python implementation:

def factorial(n):
    if n < 0:
        raise ValueError("Factorial is undefined for negative integers")
    if n == 0:
        return 1
    return n * factorial(n - 1)

For factorial(4), the calls expand as:

The call for factorial(0) returns 1. The pending calls then return in reverse order, producing:

The base case prevents further calls, while the recursive case reduces by one each time.

The function adds the integers from down to . Its base case returns 0 when n == 0.

For mystery(4), the calls expand as follows:

• mystery(4) returns 4 + mystery(3).
• mystery(3) returns 3 + mystery(2).
• mystery(2) returns 2 + mystery(1).
• mystery(1) returns 1 + mystery(0).
• mystery(0) returns 0.

The calls then complete in reverse order:

• mystery(1) returns .
• mystery(2) returns .
• mystery(3) returns .
• mystery(4) returns .

Thus, the final output is 10. In general, for a non-negative integer , the function calculates:

The Fibonacci sequence is defined by:

and, for ,

Recursive implementation:

def fibonacci(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

For example, fibonacci(5) returns 5. The function uses two base cases and makes two recursive calls for larger values.

Efficiency:

• The basic solution repeatedly calculates the same Fibonacci values.
• Its running time grows exponentially, approximately .
• Its recursion depth is .
• It can be improved using memoization, which stores previously computed values, reducing the time complexity to .
• An iterative solution is generally more memory-efficient for this problem.

The last digit of a non-negative integer n is obtained using n % 10, and the remaining digits are obtained using n // 10.

Recursive function:

def digit_sum(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

Explanation:

• Base case: If n < 10, it contains only one digit, so the function returns n.
• Recursive case: Add the last digit to the sum of the remaining digits.

For digit_sum(4725):

The integer becomes smaller after every call, so the recursion reaches the base case.

Euclid's algorithm is based on the property:

The process ends when the second value becomes zero. At that point:

Recursive implementation:

def gcd(a, b):
    a, b = abs(a), abs(b)
    if b == 0:
        return a
    return gcd(b, a % b)

For gcd(48, 18), the calls are:

• gcd(48, 18) becomes gcd(18, 12) because .
• gcd(18, 12) becomes gcd(12, 6).
• gcd(12, 6) becomes gcd(6, 0).
• gcd(6, 0) returns 6.

Thus, . The algorithm is efficient because the second argument decreases rapidly; its time complexity is logarithmic in the smaller input for typical analysis.

Both recursion and iteration can repeat a computation, but they do so differently.

Recursion:

• A function calls itself on a smaller subproblem.
• It requires a base case to terminate.
• Each call creates a new stack frame.
• It often produces clear solutions for trees, divide-and-conquer algorithms, backtracking, and recursively defined mathematics.
• It may consume more memory and can reach Python's recursion limit.

Iteration:

• Repetition is controlled using loops such as for and while.
• State is updated within the same function call.
• It is usually faster and more memory-efficient in Python.
• It is well suited to straightforward repetition, counting, and sequential processing.

For factorial, recursion expresses naturally, while a loop avoids multiple function calls. Python does not perform tail-call optimization, so deeply recursive solutions still use stack space. The appropriate approach depends on clarity, problem structure, input size, and memory requirements.

Infinite recursion occurs when recursive calls continue without reaching a terminating base case. It can result from a missing base case, an incorrect condition, or failure to move toward the base case.

Faulty example:

def repeat(n):
    print(n)
    repeat(n + 1)

This function has no base case. Every call creates a new stack frame. Python limits the depth of recursion, so it eventually raises a RecursionError rather than continuing indefinitely.

To avoid infinite recursion:

• Define a clear and reachable base case.
• Ensure each recursive call reduces or simplifies the problem.
• Validate arguments that fall outside the expected domain.
• Test boundary values such as 0, 1, negative values, and empty collections.
• Use iteration when the required recursion could be very deep.

For example, a countdown should call countdown(n - 1) and stop when n <= 0. Calling it with n + 1 would move away from the terminating condition.

A palindrome reads the same from left to right and right to left. Examples include "level" and "madam".

Recursive implementation:

def is_palindrome(text):
    text = text.lower()
    if len(text) <= 1:
        return True
    if text[0] != text[-1]:
        return False
    return is_palindrome(text[1:-1])

Explanation:

• If the string has zero or one character, it is a palindrome; this is the base case.
• If the first and last characters differ, the function immediately returns False.
• If they match, the function recursively checks the substring without those two characters.

For "level", the comparisons are:

• l equals l, so check "eve".
• e equals e, so check "v".
• "v" satisfies the base case, so the result is True.

For phrases containing spaces or punctuation, the input should first be normalized by removing non-alphanumeric characters.

In a recursive function, return performs two important tasks:

• It terminates the current function call.
• It sends a value back to the call that invoked it.

Each recursive call receives its own stack frame, containing its parameters and local variables. Calls continue to be placed on the call stack until a base case returns. The stack then unwinds in reverse order.

Consider:

def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

For power(2, 3), the calls expand to:

The base case returns 1. The pending calls then return 2, 4, and finally 8. Omitting return before the recursive expression would cause the outer calls to receive None, making the calculation fail.