Aamer Khan

Title: Recursive Programming in C++ What is Recursion OR What is Recursive Programming? Recursion or Recursive Programming is a problem-solving programming technique. We take an instance of the given problem i.e. the base case and find its solution. This solution to the base case, when used repeatedly, leads to the solution of the bigger problem. Recursion is the process of calling a function within itself. A recursive function calls itself, directly or indirectly, which is a never-ending process just like a loop. How does a recursive function work? Recursion in C++ A recursive function in C++ solves the base case of a bigger problem and calls itself at the end, which creates an unending loop. A termination condition in the main code limits the number of repetitions of the function calls. A recursive call leads toward the base case, which is either already resolved or easier to resolve. Types of Recursion: 1. Tail-Recursion - In tail-recursion, a recursive call is the last thing executed. 2. Direct Recursion - Function calls itself within the same function. 3. Indirect Recursion - Function calls another which consequently calls the first function. Why programmers use recursion? 1. Problem Solving: Solve big problems by breaking them into smaller instances. Solve the base case and use it for the solution to the bigger problem. 2. Re-Use: Some functions need to run more than one time. Do this using a recursive function that calls itself creating a loop. 3. An Alternative for Loops: Recursive functions are easier to write. They make the code simpler by eliminating the excessive use of loops. When does recursion not work in programming? Recursion does not work when a Stack Overflow error occurs. Stack Overflow Error: When the termination condition doesn't meet, or it is not defined. In this case, the recursive function will have infinite calls to itself causing a Stack Overflow error. Recursive Programming VS Iterative Programming: A recursive function is a block of code, with a solution to the instance of the problem, that calls itself until it reaches a termination condition. Whereas, in an iterative function, a set of instructions in a sequence repeat for a specified number of times or until it meets a certain condition. Recursive Programming Advantages VS Recursive Programming Disadvantages Pros of Recursion: 1. It is easier to write. 2. It makes the code simpler. 3. Some problems are naturally recursive - Tree traversals, Tower of Hanoi, etc. Cons of Recursion: 1. It takes more memory space (Stack is in use until it meets a termination condition). 2. It takes more execution time (repetitive function calls and returns take more time). Examples of Recursive Programming: Theoretical Example of Recursion (Case Scenario) Suppose your employer gives you a task to write code using recursion to teach a machine how to walk, which is easy for humans but not for the machine. You can break down the complex problem of walking into its smaller instance (base case) - taking a step. You can then use this recursive function of taking a step repeatedly (as many times as you want) to complete the task of walking. Practical Examples of Recursive Programming in C++ Following are some recursive programming language algorithm examples: Recursive Programming Algorithm Examples C++ Example 1: Recursive Factorial Function: Below is the code snippet for calculating the factorial in C++ programming language using the recursion method. Code Snippet: Code Output: The recursive code above, when compiled, gives the following output: Explanation of Recursive ‘fact’ Function: The ‘else statement’ explains how the recursive factorial function will work. The ‘main’ subprogram calls the recursive ‘fact’ function. It multiplies the number ‘x’ with its preceding number and calls itself creating a loop. The ‘if statement’ is the base case or the termination condition, which when reached gives the output. Else (x>1) return x*fact(x-1); (Multiply input number x with its preceding number) The above ‘else’ condition keeps calling the recursive ‘fact’ function for integers greater than 1. Each time the integer is multiplied by its preceding number until it fulfils the ‘if’ condition. If (x<=1) return 1; (Base Case/Termination Condition) Example 2: Recursive Fibonacci Series Below is the code snippet for calculating the Fibonacci series in C++ programming language using the recursion method. Code Snippet: Code Output: The recursive code above, when compiled, gives the following output: Explanation of Recursive ‘fibona’ Function: The ‘else statement’ explains how the recursive ‘fibona’ function will work. The ‘main’ subprogram calls the recursive ‘fibona’ function. It adds the number fibona(f-1) to fibona(f-2) and calls itself creating a loop. The ‘if statement’ is the base case or the termination condition, which when reached gives the output. Else (f>1) return fibona(f-1) + fibona(f-2); (Add the number fibona(f-1) to fibona(f-2) The above ‘else’ condition keeps calling the recursive ‘fibona’ function for integers greater than 1. Each time the integer preceded by the input number ‘f’ i.e. fibona(f-1) adds to its preceding number fibona(f-2) until it fulfils the ‘if’ condition. If (f==1) || (f==0) return (f); (Base Case/Termination Condition) The Best Recursive Programming Language It is difficult to declare the best recursive programming language. But, functional languages are usually better at handling recursion than the procedural languages. It is due to the following reasons: 1. Tail-Call Optimization - optimizing the repetition of function calls. 2. Lazy Evaluation - actual ‘work’ delayed until required. 3. Immutability - states of objects don’t change. They optimize the compilation of recursive functions in the code. The Functional Programming Languages include Lisp, Python, and Haskell, etc. Terminology: Function: A reusable block of Code that executes only when called. Call: Calling a function implies that the main code needs the use (execution) of the function. Programming Language: A programming language is a language that a compiler can interpret. _________________________________________________________________________ Sources: W3Schools, GeeksForGeeks, SparkNotes, CPlusPlus, StackExchange, Programmiz