Swipe to show menu

Recursion

Definition

Recursion is a programming technique where a function calls itself to solve a problem in smaller parts. It's especially useful for problems with repetitive structure or natural sub-problems.

The key elements of recursion are:

Base case: the condition that stops the recursion;
Recursive case: the part where the function calls itself with a simpler input.

Why use recursion?

Some problems can be naturally expressed in terms of smaller subproblems. Recursion provides a clean and elegant way to solve these by having a function call itself to handle the simpler cases. It is commonly used in tasks like processing trees, exploring paths, or breaking down structures (e.g., lists, strings).


              1234567
            
def print_message(message, times):
    if times > 0:    # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)    # Recursive case

# Function call
print_message("Hello, Recursion!", 3)

Let's go step by step through how this recursive program works:

Condition Check: if times > 0, the function proceeds. In this case, times = 3, so the condition is true;
Print Message: the function prints "Hello, Recursion!";
Recursive Call: the function calls itself with times - 1;
Repetition: this process continues until times equals 0;
Termination: when the condition times > 0 is no longer true, the recursion stops, and the program completes.

Result: The message "Hello, Recursion!" is printed three times.

Understanding the flow:

Each time the function calls itself, it adds a new frame to the call stack (a memory structure that keeps track of active function calls). The function keeps calling itself with a smaller times value. Once it reaches the base case (times == 0), it stops. Then, each previous call completes one by one in reverse order. This backtracking behavior is essential to how recursion works.

Task

Swipe to start coding

Given a string representing a phone number, which may contain spaces, dashes, parentheses, or other non-numeric characters. The goal is to extract only the digits using recursion.

If the input string number is empty, return an empty string.
Check if the first character of the string number is a digit using the isdigit() method in an if condition.
If it is a digit, concatenate it with the result of a recursive call to format_phone_number, passing the substring starting from the second character.
If it is not a digit, make a recursive call to format_phone_number, skipping the first character.

Solution

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Thanks for your feedback!

Section 5. Chapter 1

Ask AI

Ask anything or try one of the suggested questions to begin our chat

Recursion

Definition

Recursion is a programming technique where a function calls itself to solve a problem in smaller parts. It's especially useful for problems with repetitive structure or natural sub-problems.

The key elements of recursion are:

Base case: the condition that stops the recursion;
Recursive case: the part where the function calls itself with a simpler input.

Why use recursion?


              1234567
            
def print_message(message, times):
    if times > 0:    # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)    # Recursive case

# Function call
print_message("Hello, Recursion!", 3)

Let's go step by step through how this recursive program works:

Condition Check: if times > 0, the function proceeds. In this case, times = 3, so the condition is true;
Print Message: the function prints "Hello, Recursion!";
Recursive Call: the function calls itself with times - 1;
Repetition: this process continues until times equals 0;
Termination: when the condition times > 0 is no longer true, the recursion stops, and the program completes.

Result: The message "Hello, Recursion!" is printed three times.

Understanding the flow:

Task

Swipe to start coding

If the input string number is empty, return an empty string.
Check if the first character of the string number is a digit using the isdigit() method in an if condition.
If it is a digit, concatenate it with the result of a recursive call to format_phone_number, passing the substring starting from the second character.
If it is not a digit, make a recursive call to format_phone_number, skipping the first character.

Solution

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Thanks for your feedback!

Section 5. Chapter 1

Switch to desktop for real-world practiceContinue from where you are using one of the options below