EE219 Recursion in C/C++ PDF

EEN1021 (EE219) Recursion in C/C++ Slides by: Dr Conor McArdle Presented by: Dr Brendan Hayes School of Electronic Engineering [email protected] Recursion vs Iteration Many calculations and procedures we implement in computer code involve iteration, that is, executing a loop that...

EEN1021 (EE219) Recursion in C/C++ Slides by: Dr Conor McArdle Presented by: Dr Brendan Hayes School of Electronic Engineering [email protected] Recursion vs Iteration Many calculations and procedures we implement in computer code involve iteration, that is, executing a loop that repeats some basic program step a given number of times, or until we meet some condition. Examples: (1) Calculating the sum of a set of a numbers by iterating through an array, accumulating the sum at each step. (2) Searching for a word in a piece of text by iterating, word by word, through the text until we find the search term or reach the end of the text. There is another type of fundamental technique for designing a computing procedure, called recursion. Recursion is implemented as a function which calls itself, in such a way that a given problem is solved by solving a sequence of smaller versions of the same problem, until we reach a problem small enough to be solved trivially. It is the nature of some problems that a recursive method can provide a much more natural (and more easily implemented) Recursion Example #1 – Factorials Computing the factorial of an integer by iteration: where and, by definition,. Can easily write an iterative procedure in C++ to calculate the factorial, by directly applying the iterative formula : long factorial(int N) { long fact = 1; for (int i=1; i