Aprenda Recursion | Some Advanced Topics

Recursion in programming refers to the technique where a function calls itself to solve a smaller instance of the same problem. It is a powerful and elegant way to solve problems that can be broken down into smaller subproblems of the same type.

Recursive functions typically consist of two components:

Base Case: It defines the termination condition for the recursive function. When the base case is reached, the function stops calling and returns a specific value. This is necessary to prevent infinite recursion.
Recursive Case: It defines the logic for breaking down the problem into smaller subproblems and calling the function recursively with the reduced inputs. The recursive case allows the function to make progress toward the base case.

Note

The factorial of a number n is defined as follows:

n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main.cpp


              12345678910111213141516171819
            
#include <iostream>

// Function to calculate factorial
int factorial(int n)
{
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1)
        return 1;

    // Recursive case: multiply n with factorial of (n-1)
    std::cout << "Recursive Case: " << n << " * factorial(" << n - 1 << ")" << std::endl;
    return n * factorial(n - 1);
}

int main()
{
    // Call the function
    std::cout << factorial(5) << std::endl;
}

Base Case: The base case is when the input n equals 0 or 1. In this case, the factorial is defined as 1. The base case ensures that the recursion terminates and prevents infinite recursion.

Recursive Case: The recursive case is the logic for calculating the factorial of n when n is greater than 1. It involves calling the factorial function recursively with n - 1 as the argument and multiplying it with n. This reduces the problem to a smaller subproblem by computing the factorial of a smaller number.

Call the function with argument equals 5. Here is step-by-step process:

factorial(5) calls factorial(4) and multiplies the result by 5.
factorial(4) calls factorial(3) and multiplies the result by 4.
factorial(3) calls factorial(2) and multiplies the result by 3.
factorial(2) calls factorial(1) and multiplies the result by 2.
factorial(1) is the base case and returns 1.
the multiplication continues back up the chain, resulting in the final factorial of 5 that equals 120.

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 4. Capítulo 3

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Suggested prompts:

Can you explain how recursion works with another example?

What are some common mistakes to avoid when using recursion?

Can you show how to convert a recursive function to an iterative one?

Awesome!

Completion rate improved to 5

Deslize para mostrar o menu