Recursion
Explore recursion in C++ programming by understanding how functions call themselves to solve problems through smaller subproblems. Learn the concept of base cases, trace recursive calls using factorial and Fibonacci examples, and understand the advantages and drawbacks of recursion. This lesson helps you gain clarity on recursive logic and its implementation in C++.
We'll cover the following...
Introduction
Recursion is a programming technique in which a function calls itself. If the problem can be divided into smaller versions, the function can call itself with these smaller subproblems.
The concept of dividing a problem into smaller versions is not uncommon. We have encountered it several times in school math, for instance, when calculating the factorial.
Factorial of a number
Let’s take an example. A factorial of a number N, denoted by N!, is the product of all positive integers less than or equal to N. 4! would be 4 x 3 x 2 x 1.
Can we represent factorial in terms of a smaller version of itself? Yes! because 4! is simply 4 x 3!
Each recursive call tackles a simpler version of the original problem. This process continues until a base case is reached, which is a simple condition that can be solved directly without further recursion. What do you think is the base case of factorial? A factorial of 1 and 0 is 1.
Let’ ...