Recursion can be direct or indirect. It is direct when a function calls itself and it is indirect recursion when a function calls another function that then calls the first function. To illustrate solving a problem using recursion, consider the Fibonacci series: - 1,1,2,3,5,8,13,21,34... The way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2. Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition. The algorithm to use is this: 1. Ask the user for a position in the series. 2. Call the fib () function with that position, passing in the value the user entered. 3. The fib () function examines the argument (n). If n < 3 it returns 1; otherwise, fib () calls itself (recursively) passing in n-2, calls itself again passing in n-1, and returns the sum. If you call fib(1), it returns 1. If you call fib(2), it returns 1. If you call fib(3), it returns the sum of calling fib(2) and fib(1). Because fib(2) returns 1 and fib(1) returns 1, fib(3) will return 2. If you call fib(4), it returns the sum of calling fib(3) and fib(2). We've established that fib(3) returns 2 (by calling fib(2) and fib(1)) and that fib(2) returns 1, so fib(4) will sum these numbers and return 3, which is the fourth number in the series. Taking this one more step, if you call fib(5), it will return the sum of fib(4) and fib(3). We've established that fib(4) returns 3 and fib(3) returns 2, so the sum returned will be 5. Write a code in c++ programming that will implement the above algorithm.
Recursion can be direct or indirect. It is direct when a function calls itself and it is indirect recursion when a function calls another function that then calls the first function. To illustrate solving a problem using recursion, consider the Fibonacci series: - 1,1,2,3,5,8,13,21,34...
The way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2.
Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition. The
1. Ask the user for a position in the series.
2. Call the fib () function with that position, passing in the value the user entered.
3. The fib () function examines the argument (n). If n < 3 it returns 1; otherwise, fib () calls itself (recursively) passing in n-2, calls itself again passing in n-1, and returns the sum.
If you call fib(1), it returns 1. If you call fib(2), it returns 1. If you call fib(3), it returns the sum of calling fib(2) and fib(1). Because fib(2) returns 1 and fib(1) returns 1, fib(3) will return 2. If you call fib(4), it returns the sum of calling fib(3) and fib(2). We've established that fib(3) returns 2 (by calling fib(2) and fib(1)) and that fib(2) returns 1, so fib(4) will sum these numbers and return 3, which is the fourth number in the series. Taking this one more step, if you call fib(5), it will return the sum of fib(4) and fib(3). We've established that fib(4) returns 3 and fib(3) returns 2, so the sum returned will be 5.
Write a code in c++
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
