[wpseo_breadcrumb]

Output of the following C++ Program [closed]

Solutons:


It works exactly like this non-recursive translation:

int func_0() { return 2; }

int func_1() { return 3; }

int func_2() { return func_1() + func_0(); } // Returns 3 + 2 = 5

int func_3() { return func_2() + func_1(); } // Returns 5 + 3 = 8

int func_4() { return func_3() + func_2(); } // Returns 8 + 5 = 13

int func_5() { return func_4() + func_3(); } // Returns 13 + 8 = 21

int main()
{
    std::cout << func_5() << std::endl;
}

You can predict your output by following each step manually. In your case, each func call would work like the following chart:

func(5)
  +
  +--+ func(4)
  |      +
  |      +--+ func(3)
  |      |      +
  |      |      +--+ func(2)
  |      |      |      +
  |      |      |      +--+ func(1) = 3
  |      |      |      |
  |      |      |      +--+ func(0) = 2
  |      |      |
  |      |      +--+ func(1)        = 3
  |      |
  |      +--+ func(2)
  |             +
  |             +--+ func(1)        = 3
  |             |
  |             +--+ func(0)        = 2
  |
  +--+ func(3)
         +
         +--+ func(2)
         |      +
         |      +--+ func(1)        = 3
         |      |
         |      +--+ func(0)        = 2
         |
         +--+ func(1)               = 3
                              +-----------+
                                     21

As the code is very small, you can predict the output by walking through the program physically, or you could use a debugger to step through.

Main is the entry point of your program; So the very first line that you should start with is std::count<<funct(5)<<std::end1;.

You enter the func(int x) method with an initial parameter x of 5. This function looks at the parameter and returns 2 or 3 if x is 0 or 1, respectively. Otherwise, it will recursively call itself, returning the sum of func(x-1) and func(x-2).

Stepping through you get the following execution order:

func(5)
    func(4)
        func(3)
            func(2)
                func(1)
                    return 3
                func(0)
                    return 2
            func(1)
                return 3
        func(2)
            func(1)
                return 3
            func(0)
                return 2
    func(3)
        func(2)
            func(1)
                return 3
            func(0)
                return 2
        func(1)
            return 3

Which translates to -> 3 + 2 + 3 + 3 + 2 + 3 + 2 + 3 = 21

If you aren’t too familiar with recursion in programming, the concept should already be vaguely familiar. You almost certainly have come across the
Fibonacci Sequence, where the next number in the sequence is the sum of the previous two (with the first two numbers of the sequence defined as 0 and 1). The program you presented is very similar to the Fibonacci Sequence, however, it uses 2 and 3 as the first two numbers.

Hence, if you define the recursive sequence as a0 = 2, a1 = 3, then an = an-1 + an-2, which looks very similar to the function defined.

Related Solutions

What is D-Bus practically useful for?

dbus does exactly what you said: it allows two-way communication between applications. For your specific example you mentioned terminator. From terminator's man page, we see: --new-tab If this is specified and Terminator is already running, DBus will be used to...

How to check ‘mdadm’ RAIDs while running?

The point of RAID with redundancy is that it will keep going as long as it can, but obviously it will detect errors that put it into a degraded mode, such as a failing disk. You can show the current status of an array with mdadm --detail (abbreviated as mdadm...

What is a “toast notification”?

A Toast is a non modal, unobtrusive window element used to display brief, auto-expiring windows of information to a user. Android OS makes relatively heavy use of them. Here's an example of a Google Chrome toast notification on Mac OS X: A list of descriptions...

Which elliptic curve should I use?

You are misreading Bernstein and Lange's advice (admittedly, their presentation is a bit misleading, with the scary red "False" tags). What they mean is not that some curves are inherently unsafe, but that safe implementation of some curves is easier than for...

How can I find files that are bigger/smaller than x bytes?

Use: find . -type f -size +4096c to find files bigger than 4096 bytes. And : find . -type f -size -4096c to find files smaller than 4096 bytes. Notice the + and - difference after the size switch. The -size switch explained: -size n[cwbkMG] File uses n units of...

Relative imports in Python 3

Explanation From PEP 328 Relative imports use a module's __name__ attribute to determine that module's position in the package hierarchy. If the module's name does not contain any package information (e.g. it is set to '__main__') then relative imports are...

How to add a class to a given element?

If you're only targeting modern browsers: Use element.classList.add to add a class: element.classList.add("my-class"); And element.classList.remove to remove a class: element.classList.remove("my-class"); If you need to support Internet Explorer 9 or lower: Add...

less searches are always case-insensitive

I'm not sure how to enable this from the command line but when you're inside of less you can toggle the behavior you want by giving the -i command to less. toggling -i                searching for /blah and /BLAH               searching for /Blah       ...

Is using nested try-catch blocks an anti-pattern?

This is sometimes unavoidable, especially if your recovery code might throw an exception. Not pretty, but sometimes there are no alternatives. I don't think its an antipattern, just widely misused. Most nested try catch's are indeed avoidable and ugly as hell,...

Create a branch in Git from another branch

If you like the method in the link you've posted, have a look at Git Flow. It's a set of scripts he created for that workflow. But to answer your question: git checkout -b myFeature dev Creates the MyFeature branch off dev. Do your work and then git commit -am...

How can I set customise settings for htop?

htop has a setup screen, accessed via F2, that allows you to customize the top part of the display, including adding or removing a "Load average" field and setting it's style (text, bar, etc.). These seem to be auto saved in $HOME/.config/htop/htoprc, which...

Is there any way to manually bring up the keyboard?

As I see an alternative keyboard may solve your issue, and this seems to be an acceptable solution, and you even mention something you cannot find -- hereby I proudly present: Hacker's Keyboard Checking its Guide, there's in fact a section suggesting such a...

How to get rid of “No match found” when running “rm *”

This behaviour is controlled by several of Zsh's globbing options. By default, if a command line contains a globbing expression which doesn't match anything, Zsh will print the error message you're seeing, and not run the command at all. You can disable this in...

How to append date to backup filename

This isn't working because the command date returns a string with spaces in it. $ date Wed Oct 16 19:20:51 EDT 2013 If you truly want filenames like that you'll need to wrap that string in quotes. $ touch "foo.backup.$(date)" $ ll foo* -rw-rw-r-- 1 saml saml 0...

What does __all__ mean in Python?

Linked to, but not explicitly mentioned here, is exactly when __all__ is used. It is a list of strings defining what symbols in a module will be exported when from <module> import * is used on the module. For example, the following code in a foo.py...