Przerobienie zwykłej funkcji na funkcję rekurencyjną

Witam. Takie najprostsze zadania z rekurencji jak silnia, czy ciąg Fibonacciego zrobię, ale znowu mam problem z rekurencją. Użytkownik ma podać liczbę n. Funkcja(rekurencyjna) o argumencie n ma zwrócić wartość elementu o indeksie n ciągu zdefiniowanego tak:
a0=1
a1=1
an=a0+a1+a2+a3+...an-1 dla n>1

Kod mam ale bez rekurencji.
Wypisuje wszystkie indeksy dla podglądu czy wszystkie indeksy dobrze liczy.
Nie wiem jak to przekształcić na rekurencje.

#include<iostream>
#include<conio.h>
using namespace std;
int funkcja(int n);
int main(){
int liczba;
cout<<"Podaj liczbe: ";
cin>>liczba;
funkcja(liczba);
getch();
return 0;
}
int funkcja(int n){
	int m=n+1;
	int tab[m];
	for(int i=0; i<m; i++){
		if(i==0){
		tab[i]=1;
	}
	else if(i==1){
		tab[i]=1;}
		else{
		tab[i]=0;}
	}
	if(n>1){
		for(int i=2; i<m; i++){
			for(int j=0; j<i; j++)
			tab[i]=tab[j]+tab[i];
		}
	}
	for(int i=0; i<m; i++){
		cout<<tab[i]<<endl;
	}
}

Czemu int funkcja ... ?

Musisz sobie zapisać tę funkcję w taki sposób, abyś mógł obliczyć f(x) tylko dzięki znajomości f(y), gdzie y < x.

Np. potęgę całkowitą liczby 2 możesz zapisać jako
f(x) = 2 * 2 * 2 * 2 *... * 2 // x razy
lub przekształcić to do
f(x) = 2 * f(x-1)

PS: masz tragiczne formatowanie.

@adrian.widzew ale gdzie jest problem? Widzisz przeciez że
ai = a0+a1+...+ai-1 oraz
ai+1 = (a0+a1+...+ai-1) + ai
więc siłą rzeczy
ai+1 = ai + ai = 2*ai
Czyli po cofnięciu indeksu masz
an = 2*an-1

int funkcja(int n) { return n<2?1:1<<(n-1); }

@adrian.widzew w ogóle cię nie rozumiem. Chcesz to zapisać w postaci rekurencyjnej? f(n) = 2*f(n-1). Chcesz to po prostu liczyć jak człowiek? f(n) = 2^(n-1). Bo ja w ogóle cię nie rozumiem. A ten twój kod wyżej to jest WTF roku...